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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 30
作問者 : 37zigen37zigen / テスター : CuriousFairy315CuriousFairy315
15 ProblemId : 3679 / 出題時の順位表
問題文最終更新日: 2019-12-03 17:51:08

問題文

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

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

入力

$X$ $Y$ $Z$

$X,Y,Z\in\mathbb{Z}$
$0\leq X\leq10^5$
$0\leq Y\leq10^5$
$0\leq Z\leq10^6$

出力

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

サンプル

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

$(0,0,0)\to(1,1,0)$
$(0,0,0)\to(1,0,0)\to(1,1,0)$
$(0,0,0)\to(0,1,0)\to(1,1,0)$
の$3$通り。

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

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

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

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

mod $10^9+7$を取ること。

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

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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。