2080 - 二进制序号
Description

给定N位的二进制序号，请你计算偶数个二进制1的有多少个！

如果数字太多，请输出mod 10007的值！

Input

一个数字n表示二进制的长度

Output

一个数字k表示个数

Examples

Input

​2

Output

2

Input

3

Output

4
Hint

n\leq 10^7

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过次数 0
讨论
统计
上一题
下一题