配点 : $300$ 点

問題文

長さ $L$ の鉄の棒が東西方向に横たわっています。この棒を $11$ 箇所で切断して、$12$ 本に分割します。このとき分割後の各棒の長さが全て正整数になるように分割しなければなりません。 分割のしかたが何通りあるかを求めてください。二つの分割の方法は、一方で分割されているが他方で分割されていない位置が存在する場合に、そしてその場合に限って区別されます。 なお、この問題の制約下で答えは $2^{63}$ 未満であることが証明できます。

制約

• $12 \le L \le 200$
• $L$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$L$

出力

分割のしかたが何通りあるかを表す整数を出力せよ。

12

1

全て長さ $1$ の棒になるように切断する $1$ 通りです。

13

12

ちょうど一つだけ長さ $2$ の棒ができますが、切断後の $12$ 本のうち西から何番目の棒が長さ $2$ になるように切断するかで $12$ 通りの切断方法があります。

17

4368