問題一覧 > 通常問題

No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : 37zigen / テスター : CuriousFairy315
18 ProblemId : 3679 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-03 17:51:08

問題文

20XX年…、yukicoderからyuki箱君（左上のロゴ）が姿を消した。
人工知能の暴走によりyuki箱君は自我を持ち始め、yukicoderから逃げ出したのだ。

yuki箱君は任意の(a,b,c)≠0なる非負整数a,b,c,x,y,zに対して 座標(x,y,z)から座標(x+a,y+b,z+c)にワープすることができる。
原点(0,0,0)から(X,Y,Z)に移動する経路数をmod109+7で数えよ。

入力

X Y Z

X,Y,Z∈Z
0≤X≤105
0≤Y≤105
0≤Z≤106

出力

最後に改行してください。

サンプル

サンプル1
入力
1 1 0
出力
3

(0,0,0)→(1,1,0)
(0,0,0)→(1,0,0)→(1,1,0)
(0,0,0)→(0,1,0)→(1,1,0)
の3通り。

サンプル2
入力
1 1 1
出力
13
(1,1,0),(1,0,1),(0,1,1)のいずれかを経由する経路はサンプル1より9通り。
これ以外の経路は
(0,0,0)→(1,1,1)
(0,0,0)→(1,0,0)→(1,1,1)
(0,0,0)→(0,1,0)→(1,1,1)
(0,0,0)→(0,0,1)→(1,1,1)
の4通り。よって合計で13通り。

サンプル3
入力
10 0 0
出力
512

それぞれ(1,0,0),(2,0,0),…,(9,0,0)を経由するかどうかで29=512通り。

サンプル4
入力
31 53 6000
出力
882313923

mod 109+7を取ること。

サンプル5
入力
0 0 0
出力
1

yuki箱君は原点に留まり続ける。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。