問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : 37zigen37zigen / テスター : CuriousFairy315CuriousFairy315
18 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箱君は原点に留まり続ける。

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