题目描述

有如下函数：

$g(n)=\begin{cases}n,&& n\le1\\(2002*g(n-1)+2003*g(n-2))mod &2005,&n>1\\\end{cases}$

给定一个$n$,计算$g(n)$

输入格式

一个整数n

输出格式

一个整数表示答案

样例

9

511

数据范围

$n\le 10^6$

来源

• NOIP2005高中组初赛题
• 信息学奥赛之数学一本通
• stong9070整理