#1370. 「NOI2022」移除石子 (Removing Stones)

「NOI2022」移除石子 (Removing Stones)

Description

You're playing a little game called Removing Stones.

There are nn pile of stones in a line, with aia_i stones in the iith pile. Your task is to remove all stones by following operations:

  • Operation one: Choose one pile of stone, and remove at least 22 stones from it.

  • Operation two: Choose an interval of numbers [l,r](1lrn)[ l,r ] (1 \leq l \leq r \leq n) satisfying rl2r - l \geq 2, and remove exactly 11 stone from each of the piles in this range.

You can perform these operations any number of times and in any order, until you can no longer perform any operation. If you're able to remove all stones in the end you win.

You may have already started calculating problems, such as the count of distinct winning operation sequences. However in actual play you always find yourself losing. So you decided to have a trick up sleeve: at the beginning of the game, you'll secretly keep kk stones in hour hand. Before all the operations you are able to and must put these stones into one or several piles. You expect this will boost your win rate; although you know this might make you lose games you could have won.

Now you could freely choose a starting position of the game. Specifically, for each aia_i you could choose any integer in range [li,ri][ l_i,r_i ]. You want to calculate in how many starting positions you have at least one winning plan. Since the answer is large, you only need to output it modulo (109+7)(10^9+7). Two starting positions are distinct if and only if there exists at least one 1in\boldsymbol{1 \leq i \leq n} so that ai\boldsymbol{a_i} of the two are not equal. Note that the starting position refers to the position before you put in k\boldsymbol{k} stones.

Input Format

Read from file stone.in.

There are multiple test cases in each test.

The first line of input contains an integer TT indicating the number of test cases. Following are the test cases in order.

For each test case, the first line contains two integer n,kn,k, each indicating the number of stone piles and the number of stones to be added. The following nn lines each consists of two integer li,ril_i,r_i representing the range of initial stone count of each pile.

Output Format

Output to file stone.out.

For each test case, output a line of one integer, indicating the result of winnable position count modulo (109+7)(10^9+7).

1
4 1
0 1
0 1
0 1
0 1
14

Sample 2

See files [stone2.in](file://stone2.in) and [stone2.ans](file://stone2.ans) in the attachment.

Sample 3

See files [stone3.in](file://stone3.in) and [stone3.ans](file://stone3.ans) in the attachment.

Sample 4

See files [stone4.in](file://stone4.in) and [stone4.ans](file://stone4.ans) in the attachment.

Constraints and Hint

For 100%100\% of the tests, it is guaranteed that T10T \leq 10, 3n10003 \leq n \leq 1000, 0liri1090 \leq l_i \leq r_i \leq 10^9, 0k1000 \leq k \leq 100.

Test Number nn \leq kk \leq Special Case
131 \sim 3 55 22 ri5r_i \leq 5
454 \sim 5 10001000 00 li=ril_i=r_i
686 \sim 8 100100
9119 \sim 11 00 None
121312 \sim 13 22
141514 \sim 15 10001000 ri10r_i \leq 10
162016 \sim 20 None