410131: GYM103960 K Kalel, the Jumping Frog

Kalel is a frog that likes jumping over stones.

There are $$$N$$$ stones in a row, numbered from $$$1$$$ to $$$N$$$ from left to right. Kalel begins at stone $$$1$$$ and he wants to reach stone $$$N$$$.

At each move, Kalel can choose among $$$M$$$ types of jump. The $$$j$$$-th jump allows him to jump from stone $$$x$$$ to stone $$$x + d_j$$$ and costs $$$p_j$$$ energy points. It may happen that $$$p_j$$$ equals $$$0$$$ for some $$$j$$$. You can assume Kalel never runs out of energy.

Given $$$N$$$ and $$$K$$$, calculate in how many ways Kalel can reach stone $$$N$$$ spending at most $$$K$$$ energy points in total. Two ways are considered different if the sequence of jump choices is different. As this number can become very large, we are only interested in its remainder modulo $$$10^9$$$ (one billion).

The first line contains three integers, $$$N$$$, $$$M$$$ and $$$K$$$ ($$$1 \le N \le 10^9$$$, $$$1 \le M \le 10^5$$$, $$$0 \le K \le 400$$$). The next $$$M$$$ lines contain two integers each, the numbers $$$d_j$$$ and $$$p_j$$$ ($$$1 \le d_j \le 10$$$, $$$0 \le p_j \le K$$$).

Print a single line, containing in how many different ways Kalel can get to the rock $$$N$$$ spending a maximum of $$$K$$$ energy points, modulus $$$10^9$$$ (one billion).

5 3 10
1 3
2 0
3 1

6

100000 3 10
1 9
2 0
7 3

85449877