1299: fireworks

Hmz likes to play fireworks, especially when they are put regularly.
Now he puts some fireworks in a line. This time he put a trigger on each firework. With that trigger, each firework will explode and split into two parts per second, which means if a firework is currently in positionx, then in next second one part will be in positionx−1and one inx+1. They can continue spliting without limits, as Hmz likes.

Now there arenfireworks on the number axis. Hmz wants to know afterTseconds, how many fireworks are there in positionw?

Input contains multiple test cases.
For each test case:

• The first line contains 3 integersn,T,w(n,T,|w|≤10⁵)
• In nextnlines, each line contains two integersxiandci, indicating there arecifireworks in positionxiat the beginning(ci,|xi|≤10⁵).

For each test case, you should output the answer MOD 1000000007.

1 2 0 2 2 2 2 2 0 3 1 2

2 3