题目描述

考虑一个七段数码管，七条线段编号如下：

*---0---*
|       |
1       2
|       |
*---3---*
|       |
4       5
|       |
*---6---*

每条线段上都有一堆石子。Alice 与 Bob 在这些石子上进行游戏，Alice 先手。

每次操作时，当前玩家选择若干条线段，并从每条被选中的线段上移走至少一颗石子。被选择的线段集合必须满足：

• 非空；
• 在上图所表示的图中不包含环。

从不同线段上移走的石子数量可以不同。无法进行合法操作的玩家失败。

对每条线段 $i$，其初始石子数可以是闭区间 $[LO_i,HI_i]$ 中的任意整数。考虑所有满足这些范围的初始局面，求其中 Alice 在双方均采用最优策略时必胜的局面数量。

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $7$，表示线段数量固定为 7。

接下来 7 行，第 $i+1$ 行包含两个整数：

LO_i HI_i

分别表示第 $i$ 条线段初始石子数的下界和上界，其中 $i=0,1,\ldots,6$。

输出格式

输出一个整数，表示 Alice 必胜的初始局面数量对 $10^9+7$ 取模后的结果。

数据范围

对所有 $0\le i<7$：

• $0\le LO_i\le HI_i\le10000$。

样例 1

7
10 10
20 20
0 0
30 30
0 0
40 40
40 40

1

样例 2

7
1 1
1 1
1 1
0 0
1 1
1 1
1 1

0