描述

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位。

样例1

样例输入1

3

样例输出1

00004

限制

所有数据时限一秒。

来源

本人的原创题 ^_^