No.498 ワープクリスタル (給料日編)
タグ : / 解いたユーザー数 97
作問者 :
Tawara
/ テスター :
37zigen
問題文
Crystal City は、瞬時に別の場所に移動できるワープクリスタルが使えることで有名な街です。ただ任意の位置に移動できるわけではなく、クリスタルごとに現在地から移動できる相対位置が決まっています。
- Crystal City は正方形の区画を敷き詰めてできている街です。
各区画は整数座標 $(x,y)$ で表現され、東と北が それぞれ$x$ 軸、$y$ 軸の正の向きに対応します。 - 各クリスタルには移動できる相対位置 $(x,y)$（$x,y$ は整数）が記されており、
区画 $(X_1,Y_1)$ で使うと区画 $(X_1+x,Y_1+y)$ に移動することが出来ます。
給料をもらったばかりのクリス君は給料日前とは違って節約など考えず、
所持しているワープクリスタルのみを使って目的地に行こうと考えているようです。
あなたはそのルートが何通りあるのか気になり、計算してみることにしました。
※ クリス君は給料日で浮かれているので不必要にクリスタルを使う場合があります。
そのような場合も考慮して計算してください。（詳しくはサンプル3を参照）
追加：所持している個数でわかるように、クリスタルは一度使ったら、無くなります。
入力
$Gx \ Gy \ K $ $x_1 \ y_1 \ N_1$ $.$ $. $ $x_K \ y_K \ N_K$
入力は空白区切りで与えられます。
１行目には目的地の区画の座標 $(Gx,Gy)$、クリス君が所持しているクリスタルの種類 $K$ が与えられます。
２行目以降には、クリス君の所持するワープクリスタルの種類ごとの移動できる相対位置 $(x_i,y_i)$ と所持している個数 $N_i$が与えられます。
入力は全て整数であり、以下の制約を満たします。
$-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) $
$i \neq j$ に対し、$(x_i, y_i) \neq (x_j, y_j)$ が保証される。
出力
$(0,0)$ から $(Gx,Gy)$ までワープクリスタルのみを使ってたどり着くルートが何通りか出力して下さい。
ただし、答えが非常に大きくなる場合があるため $1000000007(10^9+7)$ で割った余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
2 2 2 1 0 2 0 2 1
出力
3
以下の３通りのルートが考えられます。
サンプル2
入力
2 2 1 1 1 15
出力
1
１種類のクリスタルを沢山持っていますが、取れるルートは結局以下の１通りです。
サンプル3
入力
1 0 2 1 0 3 -1 0 1
出力
4
浮かれているクリス君は、一旦目的地にたどり着いても更に移動を続ける場合があることに注意して下さい。
サンプル4
入力
1 0 3 -4 0 1 2 1 1 3 -1 1
出力
6
例えば以下のルートが考えられます。給料日だからってこんな無駄遣いしなくても..
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。