2099: 组合奇数
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：4
题目描述
yk最近很磋很磋，很2很2（但是yk绝不23）……于是yk也不知道怎么就遇到了一个问题，并且yk很想让人帮他做出来。问题是这样的：在组合数C(n,0)，C(n,1)，……，C(n,n-1)，C(n,n)中，有多少个奇数。
例如：当n=2时，C(2,0)=1，C(2,1)=2，C(2,2)=1；故总共有2个奇数。
例如：当n=2时，C(2,0)=1，C(2,1)=2，C(2,2)=1；故总共有2个奇数。
输入
有若干行，每行为一组测试数据，其中包含一个整数。
输出
对于每组输入，给出一个答案。
每个答案占一行，答案可能很大，你只需要输出其mod 22222223的余数即可。
每个答案占一行，答案可能很大，你只需要输出其mod 22222223的余数即可。
样例输入 复制
1
2
样例输出 复制
2
2
提示
【数据范围】
30%的数据中N≤20；
100%的数据中N≤10^300。
对于100%的数据，每组数据不超过100行。
30%的数据中N≤20；
100%的数据中N≤10^300。
对于100%的数据，每组数据不超过100行。