|
|
|
|
描述 Description |
|
|
|
SCABH会唱N首歌。他把它们排成一个金字塔。（下面是N=66的情形）
第11行 O
第10行 O O
第九行 O O O
……
第三行 O O O O O O O O O O
第二行 O O O O O O O O O O O
第一行 O O O O O O O O O O O O
他唱歌时，喜欢从第一行（即底行）的任一首出发，可以往左、右、左上、右上四个方向走（当然不能越出金字塔边界），一直到顶行为止，途中不能走重复的歌曲，他所走的路径就是他所唱的歌曲的序列。
当N不能写成(1+X)*X/2的形式，如N=74时，金字塔如下：
第12行 O
第11行 O O
第10行 O O O
……
第三行 O O O O O O O O O O O
第二行 O O O O O O O O O O O O
第一行 O O O O O O O O
即底行右部有缺。
现在他要统计歌曲序列的个数。
随着他会唱的歌曲数不断增加，金字塔也不断变形。
每多一首，序列个数也变化。
现在他要高级程序员——你来统计。
你只需告诉他答案除以70,207的余数即可。（最近他对回文素数感兴趣，他认为70,207是个美妙的数字）
（路人甲：你不会编程吗？SCABH：我很忙~）
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
仅一行，为歌曲数目N。（1<=N<=1,000,000,000）
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
仅一行，为歌曲序列的个数模70,207的余数。
注：当位数小于5位时，必须用前导0补足5位。
|
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
所有数据时限一秒。 |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1560 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
