偶数

题目描述

给定一个正整数n,请输出杨辉三角形前n行的偶数个数对1000003取模后的结果。

输入输出格式

输入格式


一个数

输出格式


结果

输入输出样例

输入样例 #1

6

输出样例 #1

6

说明

对于30%的数据,n<=4000 对于70%的数据,n<=4\*10^9 对于100%的数据,n<=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