题目描述

给定一个正整数 $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