题目背景

本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。

寂月城网站是完美信息教室的官网。地址：http://191.101.11.174/mgzd 。

题目描述

辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！

今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少；其中C是组合数（即C(n,i)表示n个物品无顺序选取i个的方案数），i取从0到n所有偶数。

由于答案可能很大，请输出答案对6662333的余数。

输入输出格式

输入格式：

输入仅包含一个整数n。

输出格式：

输出一个整数，即为答案。

输入输出样例

输入样例#1：

3

输出样例#1：

4

说明

对于20%的数据，n <= 20；

对于50%的数据，n <= 1000；

对于100%的数据，n <= 1 000 000 000 000 000 000 (10^18)

---

 

打个表就可以知道

然后再用上一条我自己都证明不了的性质

快速幂即可！（有那条性质不快速幂也可以了？）

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 typedef long long ll; 7  8 const int mod=6662333,mod_=6662332; 9 10 ll n;11 12 int quick(int a,int b){13     int sum=1;14     for(;b;b>>=1,a=1ll*a*a%mod)15         if(b&1)  sum=1ll*sum*a%mod;16     return sum;17 }18 19 int main(){20     scanf("%lld",&n);21     printf("%d\n",quick(2,(n-1)%mod_));22     return 0;23 }