背景

这就是传说中的潘多拉之泪么？幽蓝的光辉，细腻的色泽，隐约闪射着星光。

基德看着手中的宝石，迟疑片刻，正想把它放回原位，门外传来喊声：
基德在这里啊！快围过来！！（画外音：我就是那1009号小兵，立功了吧~）
基德抓起宝石，白色的滑翔翼瞬时张开，他看着天窗又一次浅浅的笑了：“想抓住我？没那么容易。”（啊……花痴啊啊……）
“谁说的。”一个冷漠却又坚定的声音响起。天窗上，再熟悉不过的脸。

名侦探柯南。你还是来了。

描述

KID：想不到OIBH还是找了你，工藤新一。

Conan：少废话，今天我要你束手就擒。

KID：呵呵。我们来个君子约定如何?
Conan：什么君子约定？
KID：（拿出一副牌）看好了，这可不是普通的扑克牌，这副扑克牌有n张，大小则从1到n，没有J\Q\K大王小王之类哦。

一阵眼花缭乱的变戏法般的洗牌后，Conan定睛一看，整副牌剩下了1，4，5，16，20，25…也就是说，对于任意一张牌k都满足k=4^i*5^j，其中i,j>=0。基德慢条斯理地洗着牌，道出游戏规则：现在我们要取牌，但是，取了某张x,则4x,5x,x/4,x/5都不能再取（如果它们在牌堆里的话，当然如果不在，或者说不存在，比如说4/5，是本来就没办法取的）。取的张数没有限制，可以取1张，2张等等。也可以不取。谁想出来的取法比较多，谁就算赢。

Conan：如果我赢了呢？
KID：那我就把宝石还回去，跟你走。

Conan：你等着瞧吧。

KID心想：我要把所有取法都想出来，让你一定输！

格式

输入格式

一个整数N，表示牌的大小上限。

输出格式

一个整数。由于取法可能会很多，KID不想记长串的数字（驾驶证号码的惨痛经历啊…），所以只要你输出总数 mod 10^8 的值就可以了。

样例1

样例输入1

5

样例输出1

5

提示

对于10%的数据,1<=n<=10
对于100%的数据,1<=n<=2^22
【样例说明】
一开始整副牌是1、2、3、4、5
洗牌后剩下1、4、5
5种方案分别是
1、不取
2、取1
3、取4
4、取5
5、取4和5

来源

银白的滑翔翼划过，华丽的身影慢慢消失在夜空中。

月圆之夜，一场智慧的角逐最终缓缓落下帏幕。基德赢了么？
神秘的潘多拉之泪依旧闪射着幽蓝的光辉。一切似乎都没有发生过。

那么，下一次，又会在什么时候呢？柯南仰望着天空，这个问题没人知道答案。

（画外音：我是1009号小兵，我们赢了么……宝石守住了……好累啊……）