#P1762. 偶数

    ID: 791 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>扩展欧几里德扩欧数论数学递归高精度

偶数

题目描述

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

输入格式

一行一个正整数 nn

输出格式

一行一个整数表示答案。

6
6

提示

对于 30%30\% 的数据,n4×103n\le 4\times 10^3

对于 70%70\% 的数据,n4×109n\le 4\times 10^9

对于 100%100\% 的数据,1n10151\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