学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2802

/*
2011-9-19
author:BearFly1990
*/
package acm.hdu.tests;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class HDU_2802 {
    public static void main(String[] args) {
        int[] a = new int[4019];
        a[1] = 1;
        a[2] = 7;
        for(int i=3;i<4019;i++)
            a[i]=(a[i-2]+3*i*i-3*i+1)%2009;
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        while(in.hasNext()){
            int n = in.nextInt();
            if(n == 0)break;
            System.out.println(a[n%4018]);
        }
    }

}