斐波那契

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

Description

斐波那契数列有如下性质

$\begin{cases} f[i]=1 &1 \le i\le 2 \\\ f[i] = f[i-1]+f[i-2] &i; \ge 3 \end{cases}$

请你求出斐波那契数列的第nn个数

Format

Input

一行,一个整数n(1≤n≤1e6)n(1 \le n \le 1e6)

Output

一行,一个整数,表述斐波那契数列的第nn个数

答案对100003100003取模

Samples

88823
73779

Hint

取模操作有以下特殊性质

  • $(a + b) \space mod \space n = (a \space mod \space n + b) \space mod \space n$
  • $(a - b) \space mod \space n = (a \space mod \space n - b) \space mod \space n$
  • $(a * b) \space mod \space n = (a \space mod \space n * b) \space mod \space n$

注意:除法不满足以上性质 请注意,本等式严格正确 (a+b)%mod=(a%mod+b%mod)%mod

2025级SYUCT-ACM新生第三次训练

未参加
状态
已结束
规则
XCPC
题目
24
开始于
2025-10-29 18:30
结束于
2025-11-10 0:00
持续时间
269.5 小时
主持人
参赛人数
152