hduoj2802F（N）F(N)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3202    Accepted Submission(s): 1106

Problem Description

Giving the N, can you tell me the answer of F(N)?

Input

Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.

Output

For each test case, output on a line the value of the F(N)%2009.

Sample Input

1

2

3

Sample Output

7

20

知識點：鴿巢原理、遞推