Giving the N, can you tell me the answer of F(N)?
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.
For each test case, output on a line the value of the F(N)%2009.