本原串

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2197
64-bit integer IO format: %I64d      Java class name: Main

Description

由0和1组成的串中,不能表示为由几个相同的较小的串连接成的串,称为本原串,有多少个长为n(n<=100000000)的本原串?
答案mod2008.
例如,100100不是本原串,因为他是由两个100组成,而1101是本原串。

Input

输入包括多个数据,每个数据一行,包括一个整数n,代表串的长度。

Output

对于每个测试数据,输出一行,代表有多少个符合要求本原串,答案mod2008.

Sample Input

1
2
3
4

Sample Output

2
2
6
12
Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .