Farmer John は牛を繁殖させています。現代技術では昔死んだ受賞雄牛を使えるので、雄牛は不要です。餌の量を選び、各牛の子牛数を制御します。同量を与えるので各牛の子牛数は同じです。一頭から数世代後に $N$ 頭にしたいのです。

$N = 12$ なら最初の牛に三頭の子を産む量の餌を与えます。次世代が繁殖できる年齢になれば各牛に四頭分を与え、最終世代は十二頭です。出産した牛は売られ、最新世代だけ残します。

各世代、一頭は少なくとも二頭を産みます。とても強い品種なので上限はありません。

整数 $N$ ($1 \le N \le 2{,}000{,}000{,}000$) に対し、一頭から最終的に $N$ 頭を得る方法は何通りですか。 $N$ 頭を得る方法数は $2{,}000{,}000{,}000$ 以下です。

入力

• 行 1：整数 $N$。

出力

• 行 1：$N$ 頭を得る方法数。

入出力例

入力 1

12

出力 1

8

注記

出力の注記

十二頭を得る方法の一つは $(2,2,3)$。第一世代に各牛二頭、第二に二頭、第三に三頭の子を産み、計十二頭です。他の七通りは $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$。

問題作成：Mihai Stroe、2002