Crys just invented a new cryptocurrency and is planning to present it at \(T\) blockchain conferences around the world. The conference schedules are already on their way to being finalized, but Crys is considering how she might get her own talks in at the last minute.

A certain conference is \(K\) hours long, with talks to start and end on the hour. Each talk will span a non-empty inclusive time interval of hours \([x, y]\), such that \(x\) and \(y\) are integers and \(0 \le x \lt y \le K\). \(N\) talks are gradually being added to the schedule, one after another, with the \(i\)th added talk scheduled to span the time interval \([S_i, S_i + D_i]\). The \(N\) talks are not necessarily added in order of starting or ending time. Their time intervals may arbitrarily overlap with one another, and are not necessarily distinct.

Each time a talk is added to the schedule, Crys will then consider submitting a request for her own talk to also be included. This involves proposing a time interval for her talk, which must similarly be an integral interval \([x, y]\) such that \(0 \le x \lt y \le K\). Crys suspects that her request would be rejected if the inclusion of her talk might prevent an attendee from hearing another talk due to her proposed time interval entirely subsuming an already-scheduled one. As such, after the first \(i\) talks have been added to the schedule, she will *not* propose a time interval \([x, y]\) if there exists any existing talk \(j\) \((1 \le j \le i)\) such that \(x \le S_j\) and \(S_j + D_j \le y\).

Letting \(C_i\) be the number of different time intervals which Crys could validly propose for her talk after the first \(i\) talks have been added to the schedule, please determine the value of \((C_1 * C_2 * ... * C_N)\) modulo 1,000,000,007.

# Constraints

\(1 \le T \le 95\)
\(1 \le N \le 300,000\)
\(1 \le K \le 1,000,000,000\)
\(0 \le S_i < K\)
\(1 \le D_i \le K\)
\(1 \le S_i + D_i \le K\)

The sum of \(N\) across all conferences is at most 1,500,000.

# Input

Input begins with an integer \(T\), the number of conferences. For each conference there are \(N + 1\) lines. The first line contains the space-separated integers \(N\) and \(K\). \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(S_i\) and \(D_i\).

# Output

For the \(i\)th conference, print a line containing *"Case #i: "*, followed by a single integer, the product of \(C_{1..N}\) modulo 1,000,000,007.

# Explanation of Sample

In the first conference, once a talk spanning time interval \([1, 2]\) exists, Crys can only propose time intervals \([0, 1]\) and \([2, 3]\) for her talk without subsuming \([1, 2]\). Therefore, \(C = [2]\).

In the second conference, after the first talk (spanning time interval \([1, 3]\)) has been added to the schedule, Crys can propose any of the time intervals \([0, 1]\), \([0, 2]\), \([1, 2]\), or \([2, 3]\). After the introduction of the second talk (spanning time interval \([0, 2]\)), she can only propose \([0, 1]\), \([1, 2]\), or \([2, 3]\). Therefore, \(C = [4, 3]\), and the final answer is (4 * 3) modulo 1,000,000,007 = 12.

In the third conference, \(C = [8, 4]\).

In the fourth conference, \(C = [4126, 3631, 3239, 2687, 2687]\).