题目描述

斐波那契数列是指这样的数列

• 数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和。

给定一个数字 $n$ 请你求出斐波那契数列第 $n$ 项的结果。由于结果可能很大，你需要对 $100003$ 取余，你只需要输出对该数字取余后的结果。

输入格式

一个整数 $n$ 代表第 $n$ 项。

输出格式

输出第 $n$ 项的数值。

4

3

40

31086

样例 2 解释

第 $40$ 项的结果实际是 $102334155$，对 $100003$ 取余后为 $31086$

数据范围

$1\leq n\leq 10^4$