Removing Stones

You are playing a game called Removing Stones.

There are n piles of stones arranged in a row. The i-th pile initially has a_i stones. You are allowed to perform two types of operations in any order and any number of times until no more operations can be performed:

• Operation 1: Choose a single pile and remove at least 2 stones from it.
• Operation 2: Choose a contiguous segment of piles with indices in the interval \([l, r]\) satisfying \(1 \le l \le r \le n\) and \(r - l \ge 2\) (i.e. at least 3 piles), and remove exactly 1 stone from each pile in that segment.

You win if, after a sequence of operations, you can remove all the stones from every pile.

However, the game has a twist. Before you start performing any operations, you must distribute exactly k extra stones (that you secretly hold) among one or more piles. The extra stones are added to the piles, so if you add x_i extra stones to pile \(i\), its stone count becomes \(a_i+x_i\) (with \(\sum_{i=1}^n x_i=k\)).

In addition, you are free to choose the initial configuration. That is, for each pile \(i\) you can choose its starting stone count \(a_i\) arbitrarily from the integer interval \([l_i, r_i]\). (Note that two initial configurations are considered different if there exists at least one \(i\) such that the chosen value \(a_i\) differs.)

Your task is to count, modulo \(10^9+7\), the number of initial configurations for which there exists at least one way to distribute the extra k stones such that you have a winning strategy (i.e. you can eventually remove all the stones by applying the operations in some order).

Important details about winning positions:

• For \(n \ge 3\): A configuration \(b=(b_1, \dots, b_n)\) (where \(b_i=a_i+x_i\)) is winning if there exists an integer \(m\) (interpreted as the minimum pile count) such that for every \(i\), either \(b_i = m\) or \(b_i \ge m+2\), and at least one pile has exactly \(m\) stones. (Any move sequence reversing the two allowed operations can reduce such a configuration to \(\mathbf{0}\) by a series of reverse moves.)
• For \(n=1,2\): Operation 2 is not available. In these cases a pile’s stone count must be either 0 or at least 2 in order to be removable (since Operation 1 can only remove \(r\) stones with \(r \ge 2\)).

Formally, for an initial configuration \(a=(a_1,\dots,a_n)\) chosen with \(a_i \in [l_i, r_i]\), you need to check whether there exist nonnegative integers \(x_1,x_2,\dots,x_n\) with \(\sum_{i=1}^n x_i=k\) such that if you define \(b_i=a_i+x_i\), then:

• If \(n \ge 3\): There exists an integer \(m\) with \(m \le b_i\) for all \(i\) and for every \(i\) it holds that either \(b_i=m\) or \(b_i\ge m+2\) (and at least one \(i\) satisfies \(b_i=m\)).
• If \(n \in \{1,2\}\): For every \(i\), it must hold that \(b_i=0\) or \(b_i \ge 2\) (note that if \(b_i=1\) then no valid move exists for that pile).

Your program should output the total count of winning initial configurations modulo \(10^9+7\).

inputFormat

The input begins with a line containing two integers n and k, where n (the number of piles) and k (the number of extra stones) satisfy the constraints given in the problem.

Then follow n lines. The i-th of these lines contains two integers li and ri (li <= ri), representing the range of allowable initial stone counts for pile i.

Note: In the test cases provided the ranges will be small enough that a brute force solution over the product of the intervals is feasible.

outputFormat

Output a single integer—the number of initial configurations (i.e. choices of ai for \(1\le i\le n\)) for which there exists a distribution of the extra k stones making it possible to eventually remove all the stones, taken modulo \(10^9+7\).

sample

1 0
0 2

2