福州大学OJ FZU 1683矩阵题

Problem 1683 纪念SlingShot

Accept: 330 Submit: 1202

Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

 已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。 

Input

第一行是一整数m，代表总共有m个cases。

Output

对于每个case，输出一行。格式见样例，冒号后有一个空格。

Sample Input

236

![](htt