No.498 Warp Crystal (Payday Edition)
Tawara
37zigenProblem Statement
Crystal City is a town famous for its warp crystals, which allow instant travel to another location.However, they cannot take you to an arbitrary location: each crystal has a fixed relative position that you can move to from your current location.
- Crystal City is a town made of square blocks laid out in a grid.
Each block is represented by integer coordinates $(x,y)$, where east and north correspond to the positive directions of the $x$-axis and $y$-axis, respectively. - Each crystal is inscribed with the relative position $(x,y)$ ($x,y$ are integers) it can move you by,
and using it at block $(X_1,Y_1)$ moves you to block $(X_1+x,Y_1+y)$.
Having just been paid, Chris, unlike before payday, has no thought of saving, and
intends to reach the destination using only the warp crystals he owns.
You became curious about how many such routes there are and decided to calculate it.
* Chris is giddy from payday, so he may use crystals unnecessarily.
Take such cases into account in your calculation. (See Sample 3 for details.)
Addendum: As the owned counts suggest, a crystal disappears once it is used.
Input
$Gx \ Gy \ K $ $x_1 \ y_1 \ N_1$ $.$ $. $ $x_K \ y_K \ N_K$
The input is given separated by spaces.
The first line contains the coordinates $(Gx,Gy)$ of the destination block and the number $K$ of types of crystals Chris owns.
From the second line onward, for each type of warp crystal Chris owns, the relative position $(x_i,y_i)$ it can move him by and the number $N_i$ of crystals he owns are given.
All input values are integers and satisfy the following constraints.
$-10^5 \le Gx, Gy \le 10^5$
$1 \le K \le 5$
$1 \le N_i \le 15$
$-10^4 \le x_i, y_i \le 10^4$ , $ (x_i, y_i) \neq (0,0) $
For $i \neq j$, it is guaranteed that $(x_i, y_i) \neq (x_j, y_j)$.
Output
Print the number of routes from $(0,0)$ to $(Gx,Gy)$ using only warp crystals.
Since the answer can be very large, print it modulo $1000000007(10^9+7)$. Print a newline at the end.
Sample
Sample 1
Input
2 2 2 1 0 2 0 2 1
Output
3
The following 3 routes are possible.
Sample 2
Input
2 2 1 1 1 15
Output
1
He has many crystals of one type, but in the end only the following 1 route is possible.
Sample 3
Input
1 0 2 1 0 3 -1 0 1
Output
4
Note that the giddy Chris may keep moving even after reaching the destination once.
Sample 4
Input
1 0 3 -4 0 1 2 1 1 3 -1 1
Output
6
For example, the following route is possible. Payday or not, he really doesn't need to be this wasteful...
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。