# Fibonacci Sequence

The Fibonacci sequence is defined in the following way. $F(0) = F(1) = 1$ and for all $N \gt 1$ we have $F(N) = F(N-1) + F(N-2)$. Given an integer $N$ ($1 \le N \le 10^4$). Calculate $F(N)$ modulo ($10^6 + 3$).

## Input format
One integer $N$ ($1 \le N \le 10^4$).

## Output format
Print one integer - $F(N)$ modulo ($10^6 + 3$).

### Sample 1
#### Input

1

#### Output

1

### Sample 2
#### Input

7

#### Output

21