---
# System prepended metadata

title: Fibonacci Sequence

---

# 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
```


