005 - 楽しい花の水やり (Watering Flower is Fun)
時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 1 /
問題
ミズゴロウのゴロウくんは, 花を育てている. 毎日水やりをすることで, 日々花は美しくなっていく.
ゴロウくんが育てている花には, 美しさ という指標がある. 花の美しさは正の整数の量であり, 最初, ゴロウくんの花の美しさは 1 である. ある日に花の美しさが B であったとする. この日に花に水を W だけやると, 翌日には花の美しさは B × W になっている. ただし水をやる量 W は正の整数である.
ゴロウくんは常に美しくなっていく花を見たいと考えており, 必ず花が今より美しくするように水をやる. すなわち, 水をやる量 W は 1 より大きい. また, ゴロウくんは最終的に花の美しさを N にしたいと考えている. ゴロウくんのために, ゴロウくんの花の美しさが N になるような水やりの通りの総数を 100000 で割ったあまりを計算するプログラムを作成せよ.
入力
入力は 1 行からなる.
1 行目に, 整数 N (2 ≦ N ≦ 1012) が入力される.
出力
1 行に, ゴロウくんの花の美しさが N になるような水やりの通りの総数を 100000 で割ったあまりを出力せよ.
入出力例
入力例 1
12
出力例 1
8
入力例 1 について, 花の美しさが 12 になるように水やりをしていく方法は下記の表の 8 通りの方法がある.
| No. | 1 日目の美しさ | 1 日目の水量 | 2 日目の美しさ | 2 日目の水量 | 3 日目の美しさ | 3 日目の水量 | 4 日目の美しさ |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 12 | 12 | - | - | - | - |
| 2 | 1 | 2 | 2 | 6 | 12 | - | - |
| 3 | 1 | 3 | 3 | 4 | 12 | - | - |
| 4 | 1 | 4 | 4 | 3 | 12 | - | - |
| 5 | 1 | 6 | 6 | 2 | 12 | - | - |
| 6 | 1 | 2 | 2 | 2 | 4 | 3 | 12 |
| 7 | 1 | 2 | 2 | 3 | 6 | 2 | 12 |
| 8 | 1 | 3 | 3 | 2 | 6 | 2 | 12 |
入力例 2
7
出力例 2
1
入力例 3
25200
出力例 3
32928
入力例 3 の制約を満たす水やりの方法は 132928 通りある. よって, これを 100000 で割ったあまりである 32928 を出力する.