最后の战

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

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

基德看着手中的宝石,迟疑片刻,正想把它放回原位,门外传来喊声:
基德在这里啊!快围过来!!(画外音:我就是那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号小兵,我们赢了么……宝石守住了……好累啊……)

怪盗基德-月下の谜模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2009-08-17 19:00
结束于
2009-08-17 22:00
持续时间
3.0 小时
主持人
参赛人数
1332