题目描述

今天小明学习了组合数，现在他很想知道 $\sum \rm{C}_{n}^{i}$ 是多少。其中 $\rm{C}$ 是组合数（即 $\rm{C}_{n}^{i}$ 表示 $n$ 个物品无顺序选取 $i$ 个的方案数），$i$ 取从 $0$ 到 $n$ 的所有偶数。

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

输入格式

输入仅包含一个整数 $n$。

输出格式

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

3

4

提示

对于 $20\%$ 的数据，$n \le 20$；

对于 $50\%$ 的数据，$n \le 10^{3}$；

对于 $100\%$ 的数据，$n \le 10^{18}$。