Description

斐波那契数列有如下性质

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

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

Format

Input

一行，一个整数$n(1 \le n \le 1e6)$

Output

一行，一个整数，表述斐波那契数列的第$n$个数

答案对$100003$取模

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$

注意:除法不满足以上性质