题目背景

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

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

题目描述

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

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

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

输入输出格式

输入格式：

输入仅包含一个整数n。

输出格式：

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

输入输出样例

3

4

说明

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

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

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

分析：先上结论：答案为2^(n-1),为什么是这个呢？如果i能取奇数，那么答案为2^n,因为我们从n个数中取0个，取1个，取2个...取n个，相当于取任意多个，每个位置可以取或者不去，那么根据乘法原理，答案就为2^n,如果i只能为偶数，就会有一半的位置取不了，答案就为原答案的1/2.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

long long n;

const int mod = ;

typedef long long LL;

LL fun(LL x, LL n)

{

    LL res = ;

    while (n > )

    {

        if (n & )

            res = (res*x) % mod;

        x = (x*x) % mod;

        n >>= ;

    }

    return res % mod;

}

int main()

{

    scanf("%lld", &n);

    printf("%lld\n",fun(, n - ));

    return ;

}