問題文


の長方形のグリッドがあります。左下から右上への最短経路のうち、経路の上側のマスの数が個であるようなものの数をで割った余りを出力してください。

例えば、のとき、以下の最短経路は条件を満たします。

例

制約


入力


入力はすべて整数である。

出力


答えを一行に出力せよ。

サンプル


入力1
2 2 2
出力1
2

つの経路が条件を満たします。

入力2
4 6 10
出力2
16

 

入力3
100 100 100
出力3
190569292

提出


Go (1.14)