# 偶数

## 题目描述

给定一个正整数 $n$，请输出杨辉三角形前 $n$ 行的偶数个数对 $1000003$ 取模后的结果。

## 输入格式

一行一个正整数 $n$。

## 输出格式

一行一个整数表示答案。

## 样例 #1

### 样例输入 #1

```
6
```

### 样例输出 #1

```
6
```

## 提示

对于 $30\%$ 的数据，$n\le 4\times 10^3$。

对于 $70\%$ 的数据，$n\le 4\times 10^9$。

对于 $100\%$ 的数据，$1\le n\le 10^{15}$。

杨辉三角形的前七行：

```plain
       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1
```