E. 斐波那契数列 Ⅱ

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输出第 $n$ 项的数值。

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

$1\leq n\leq 10^4$