偶数
题目描述
给定一个正整数 $n$，请输出杨辉三角形前 $n$ 行的偶数个数对 $1000003$ 取模后的结果。
输入输出格式
输入格式
一行一个正整数 $n$。
输出格式
一行一个整数表示答案。
输入输出样例
输入样例 #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
```