题目描述
题目描述
给定一个正整数 $n$，请输出杨辉三角形前 $n$ 行的偶数个数对 $1000003$ 取模后的结果。
输入格式
一行一个正整数 $n$。
输出格式
一行一个整数表示答案。
样例输入
6
样例输出
6
提示
对于 $30\%$ 的数据，$n\le 4\times 10^3$。
对于 $70\%$ 的数据，$n\le 4\times 10^9$。
对于 $100\%$ 的数据，$1\le n\le 10^{15}$。
杨辉三角形的前七行：
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
本题源自洛谷 P1762