SCABH会唱N首歌。他把它们排成一个金字塔。（下面是N=66的情形） 第11行O 第10行OO 第九行OOO …… 第三行OOOOOOOOOO 第二行OOOOOOOOOOO 第一行OOOOOOOOOOOO 他唱歌时，喜欢从第一行（即底行）的任一首出发，可以往左、右、左上、右上四个方向走（当然不能越出金字塔边界），一直到顶行为止，途中不能走重复的歌曲，他所走的路径就是他所唱的歌曲的序列。 当$N$不能写成$(1+X) \times X/2$的形式，如$N=74$时，金字塔如下： 第12行O 第11行OO 第10行OOO …… 第三行OOOOOOOOOOO 第二行OOOOOOOOOOOO 第一行OOOOOOOO 即底行右部有缺。 现在他要统计歌曲序列的个数。 随着他会唱的歌曲数不断增加，金字塔也不断变形。 每多一首，序列个数也变化。 现在他要高级程序员——你来统计。 你只需告诉他答案除以$70207$的余数即可。（最近他对回文素数感兴趣，他认为$70207$是个美妙的数字）

仅一行，为歌曲数目$N$。$（1 \le N \le 1,000,000,000）$

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

3 \n

00004     \n