#P8162. 「2017 山东三轮集训 Day6」A

    ID: 7270 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高普通生成函数生成函数求系数Lucas 定理阶乘逆元预处理模逆元快速幂

「2017 山东三轮集训 Day6」A

题目描述

JOHNKRAM 最近在研究集合。他从 [1,2n] [1,2n] 中任选了 n n 个不同的整数,组成了 (2nn) \binom{2n}{n} 个不同的集合。现在他想知道,在这些集合中,有多少个集合含有偶数个偶数?答案可能很大,你只需要告诉他答案 mod1000003 \mathop{\text{mod}} 1000003 的结果即可。

输入格式

一行,一个整数 n n ,意思如题所示。

输出格式

一行,一个整数 ans \text{ans} ,表示答案 mod1000003 \mathop{\text{mod}} 1000003 的结果。

7
1716

数据范围与提示

对于 30% 30\% 的数据,n≤1000003 n \leq 1000003 ;
对于 100% 100\% 的数据,1≤n≤1018 1 \leq n \leq 10 ^ {18} 。