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：我很忙~）

仅一行，为歌曲数目N。（1< =N< =1,000,000,000）

仅一行，为歌曲序列的个数模70,207的余数。
注：当位数小于5位时，必须用前导0补足5位。

3

00004