Polygon of Polygons

2 secs 1024 MB
magurofly

問題文


整数 が与えられます。

角形の 個の頂点から 個以上の頂点を選ぶとき、線で結ぶと正多角形になるような選び方は何通りありますか?

制約


  • 入力は整数である

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
6
出力例1
3

角形になる選び方が 通り、 角形になる選び方が 通りであわせて 通りあります。

入力例2
17
出力例2
1

角形になる選び方が 通りあります。

入力例3
123456789012
出力例3
102880657538

答えは ビット整数の表せる範囲を超えることがあります。

提出


Go (1.14)