A2755. SAC#1 - 组合数
编程题
普及/提高-
知识点
题目描述
今天小明学习了组合数，现在他很想知道 $\sum \rm{C}$$_{n}^{i}$ 是多少。其中 $\rm{C}$ 是组合数（即 $\rm{C}$$_{n}^{i}$ 表示 $n$ 个物品无顺序选取 $i$ 个的方案数），$i$ 取从 $0$ 到 $n$ 的所有偶数。
由于答案可能很大，请输出答案对 $6662333$ 的余数。
由于答案可能很大，请输出答案对 $6662333$ 的余数。
输入格式
输入仅包含一个整数 $n$。
输出格式
输出一个整数，即为答案。
输入输出样例
输入 #1
3
输出 #1
4
说明/提示
对于 $20\%$ 的数据，$n \le 20$；
对于 $50\%$ 的数据，$n \le 10^{3}$；
对于 $100\%$ 的数据，$n \le 10^{18}$。
对于 $50\%$ 的数据，$n \le 10^{3}$；
对于 $100\%$ 的数据，$n \le 10^{18}$。