005 - 楽しい花の水やり (Watering Flower is Fun)

時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 1 /


TLE
8sec
MLE
256MB
得点
100

問題

ミズゴロウのゴロウくんは, 花を育てている. 毎日水やりをすることで, 日々花は美しくなっていく.

ゴロウくんが育てている花には, 美しさ という指標がある. 花の美しさは正の整数の量であり, 最初, ゴロウくんの花の美しさは 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 日目の美しさ
111212 - - - -
2122612 - -
3133412 - -
4144312 - -
5166212 - -
612224312
712236212
813326212

入力例 2

7

出力例 2

1

入力例 3

25200

出力例 3

32928

入力例 3 の制約を満たす水やりの方法は 132928 通りある. よって, これを 100000 で割ったあまりである 32928 を出力する.