题目背景
左特的五十七条戒律：
第一条戒律至关重要: “要永远打胜仗”。 其他56条戒律呢?好吧.......
戒律二: “永不让的虫子嘲笑你”。
蠢货什么都嘲笑，甚至嘲笑比它们更优秀的。但注意了，笑也是会伤人的！嘲笑会像疾病一样散播，很快所有虫子都会嘲笑你。你必须迅速扑灭这种恶劣的欢愉，免得它散布开来。
戒律三: “保证休息”。
战斗和冒险会消耗你的体力。而休息的时候，身体可以恢复力量，治愈创伤。休息得越久，你就越强大。
戒律四: “忘记过去”。
过去充满痛苦，回想过去只能让你满心悲凉。想想别的东西，比如未来和美食。
戒律五: “以力降力”。
你的对手很强大? 没关系！用比他们更强大的力量对付他们，他们很快就会败下阵来。
戒律六: “我命由我”。
我们的长辈说我们的命运在出生之前就已注定。我不同意。
戒律七: “放下对逝者的执念”。
死去之后的世界会更好还是更糟?没人知道。所以我们无需心存执念。
戒律八: “独自旅行”。
你不能依赖别的虫子，没人永远忠诚。所以没人能永远和你同行。
戒律九: “保持房屋整洁”。
你自己就是你最有价值财产，而家是你的安身之所。所以要让家里干净整洁。
戒律十: “保持武器锋利”。
我会让我的武器“生命终结者”随时保持最佳状态。这样砍东西就容易多了。
戒律十一: “母亲总会犹豫计较”。
这一条不言自明。
戒律十二: “让披风保持干燥”。
披风打湿之后尽快弄干。穿湿的披风很不舒服，而且还会生病。
戒律十三: “永不恐惧”。
恐惧只能让你裹足不前。直面恐惧需要巨大的努力，第一步就是不能恐惧。
戒律十四: “尊重强者”。
尊重力量、智慧或者两者都胜于你的虫子，不得轻视或嘲笑它们。
戒律十五: “对付一个敌人只需一拳”。
一击便足以对付一个敌人，再多也是浪费。记住自己出了几拳也就能知道打败了多少敌人。
戒律十六: “不可犹豫”。
下定决心就动手，不要瞻前顾后。这样的行事方式会让你取得更多成就。
戒律十七: “相信自己的力量”。
也许有别的虫子会怀疑你，但总有一个可以永远信赖——你自己。相信自己的力量能让你永远步伐坚定。
戒律十八: “在黑暗中追寻真理”。
这条戒律也是不言自明。
戒律十九: “没有尝试，只有成功”。
如果要尝试什么事情，那就一定要达成目标。不能成功的话就是失败！要不计代价地取得成功。
戒律二十: “永不撒谎”。
和别的虫子谈话的时候，说真话既显谦恭又很高效。不过要小心，说真话可能会让你树敌。这是你必须承受的代价。
戒律二十一: “留意周围”。
不要总低着头走路！你得时不时抬起头四处看看，免得被偷袭。
戒律二十二: “不要恋巢”。
翅膀一长硬我就离开了故乡，开始探索世界。不要眷恋故巢。你会一事无成。
戒律二十三: “寻找敌人的弱点”。
所有敌人都有弱点，比如甲壳上的裂缝或是在睡梦中。你必须始终保持警惕，仔细探查敌人的弱点！
戒律二十四: “攻击敌人的弱点”。
发现敌人的弱点之后就发起攻击。它们马上就会丢盔弃甲。
戒律二十五: “保护好自己的弱点”。
小心不要被敌人发现弱点，要好好保护它们。最好的保护是什么?就是根本不要有弱点。
戒律二十六: “不要相信你的倒影”。
凝视某些闪耀的平面时，你会看到你自己的脸。那张脸会模仿你的动作，好像就是你自己。但不要相信它。
戒律二十七: “尽量多吃”。
吃饭的时候能吃多少吃多少。这能让你获得更多能量，而且能减少吃饭的次数。
戒律二十八: “不要窥视黑暗”。
如果你窥视黑暗，久久不见一物，你的心就会流连于古旧的记忆。戒律四已经说过了，我们要避开记忆。
戒律二十九: “训练方向感”。
曲折的洞穴里很容易迷路，而优秀的方向感就像装在你脑子里的魔法地图，非常有用。
戒律三十: “不要盲目轻信承诺”。
承诺有时不是很可靠，要对别的虫子所允诺的事情警惕。
戒律三十一: “病从脏处起”。
老在脏兮兮的地方待着会让你生病。去别的虫子家的时候，要让它们提供最高规格的卫生条件。
戒律三十二: “名字中含有力量”。
名字具有力量，给东西起名字就是赋予它们力量。我把自己的骨钉叫做“生命终结者”。不要盗用我想的名字！自己想！
戒律三十三: “不可尊重敌人”。
对敌人热情洋溢算不上美德！反对你的虫子不配得到你的尊重、善意和同情。
戒律三十四: “睡觉之前不要吃东西”。
睡前吃东西不好消化，还会让你睡不着。这是常识了。
戒律三十五: “上就是上，下就是下”。
在黑暗中跌倒之后就很容易失去方向感，找不到往上的路。这一条要好好记住！
戒律三十六: “蛋壳易碎”。
这条戒律还是不言自明。
戒律三十七: “管别的虫子借东西，不要借东西给它们”。
别的虫子借了不还你落得一场空，自己借了不还赚大把。
戒律三十八: “小心神秘的力量”。
我们头上有一股神秘的力量冲我们压过来，把我们往下按去。如果你在空中停留太久，那股力量就会把你压进地里，让你丢掉小命。小心啊！
戒律三十九: “快吃慢饮”。
身体非常精细，补充能量的时候得小心谨慎。吃饭地时候尽量快点，但喝水的时候就得慢下来。
戒律四十: “随心所欲，无视规则”。
过分地拘泥于规则可能会拖你后腿。有时候要灵活变通。
戒律四十一: “学会分辨谎言”。
别的虫子跟你说话的时候经常会撒谎。要无情的分辨和质疑他们，直到它们承认自己撒谎。
戒律四十二: “有钱就花”。
有些虫子是吝啬鬼，甚至会把钱带进棺材。能花的时候就花才是上策，不然享受不到生命中的各种乐趣。
戒律四十三: “永不原谅”。
如果有虫子祈求你的原谅，比如你兄弟，那就一定要拒绝。这个兄弟和其他虫子都不配得到你的原谅。
戒律四十四: “你没法在水里呼吸”。
水很提神，但试图在水里呼吸的话那感觉就糟透了。
戒律四十五: “一个东西没法变成别的东西”。
这很明显嘛，但有些虫子就是要指鹿为马。你要小心！
戒律四十六: “世界没你想象的那么大”。
你年轻的时候自然满心以为天地广阔。遗憾呐，世界实际上要小得多。这就是我走遍每一片土地之后的感触。
戒律四十七: “打造自己的武器”。
只有你自己知道你需要什么武器。我在你这么大的时候亲手用壳木打造了“生命终结者”。它从不让我失望。我对它也一样。
戒律四十八: “小心火烛”。
火是肆意狂舞的灼热精灵。它可以给你温暖，为你照明，但太过靠近的时候也会烤焦你的身体。
戒律四十九: “雕塑没有意义”。
不要崇拜雕像！又没虫子为你我立像，那我们为什么要注意这种玩意儿?
戒律五十: “不要沉溺于谜题”。
生活有时候让人疑惑。晦涩的迷题。如果不能马上发现一件事物的内涵，那就不要浪费时间去探究。继续前进即可。
戒律五十一: “万物皆有害处”。
只要有机会，任何东西都能伤害你。朋友、敌人、怪物，甚至是道路。要怀疑一切。
戒律五十二: “小心父亲的嫉妒”。
父亲很严厉，所以经常要求我们服从于他。如果你要开拓自己的道路，有时候适当地成长、反抗和表达自己也是应当的。
戒律五十三: “不要横刀夺爱”。
所有生物心中都有欲望。你要是瞥见了别的虫子欲望，那就抑制住夺走它的冲动。横刀夺爱不会给你带来快乐。
戒律五十四: “把东西锁起来的时候记得带好钥匙”。
没什么可以永远的被锁起来，所以拿好钥匙。总有一天你得回来拿走藏起来的东西。
戒律五十五: “不向任何虫折腰”。
有虫子会强迫别的虫子遵从自己的意志。他们想抢走你的食物、你的土地、你的身体，甚至你的思想！
他们凭什么白白拿走你的东西?不要屈服，绝不能听从他们的命令。
戒律五十六: “不要做梦”。
梦想是危险的东西，是不属于你的古怪念头。它们会侵蚀你的思想。但你一对抗这些念头，你的身体就会受伤！所以最好跟我一样根本不做梦。
戒律五十七: “遵从所有的戒律”。
最重要的是要把戒律铭记于心，一丝不苟地加以执行。包括这一条！
你真的把我说的话都听进去了吗？我们再重复一遍“左特的五十七条戒律”。
题目描述
左特有 n 条戒律，每条戒律可以描述为一个在 [0,2^k-1] 的整数，其中第 i 条戒律为$ a_i $。
我们称一条戒律$ x\in [0,2^k-1] $可以被 左特的戒律 表示当且仅当存在一个 左特的戒律 的非空子序列的异或和为 x 。
作为左特的小迷妹，你忘记了 左特的戒律 ，只知道 左特的戒律 无法表示 X 而且左特不说废话（$ \forall i, a_i\neq 0 $, 但可能能表示出 0 ）。
左特十分生气决定考考你对于每个$ t\in [0,2^k) $求有多少个 左特的戒律 能表示恰好 t 个戒律。
左特不想为难你，决定让你输出所有答案模 998244353 后的异或和即可
输入输出格式
输入格式
输入一行三个整数分别表示 n, k, X, 意义与题面描述一致
输出格式
输出一行表示答案
样例
样例输入1：
2 3 0样例输出1：
42样例解释：
对于所有 $ a_1 \neq a_2 $ 都满足条件且能表示 3 种戒律
其余的不存在方案，答案即为 42 异或 0
样例输入2：
1919 810 114514样例输出1：
819268765数据范围：
对于 100% 的数据满足 $1\leq n\leq 10^{9},1\leq k\leq 10^6,0\leq X\leq 10^6,X < 2^k$
对于 30% 的数据满足 $n\leq 1000,k\leq 1000$
对于 40% 的数据满足$ n\leq 100000 $
对于另外 20% 的数据满足$ k\eq 100000 $