老君的数
题号:NC22577
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

由于老君曾立下多个誓言,並写成《誓言录》,其中一个为百年之内不得离开老君阁,不得干涉外界事物,所以他整日待在蓝溪镇无所事事。
这一天,他找到了 n 个数 ,要在其中选出恰好 k 个数 ,满足 。( 表示异或运算)
求对于每一种选法的 之和模 998244353 的值。


输入描述:

第一行三个整数 n(),k(),s()。
接下来一行 n 个整数,第 i 个整数表示 A_i ()。

输出描述:

输出一个整数,表示答案。
示例1

输入

复制
6 2 6
1 2 2 4 6 7

输出

复制
5

说明

一共有 3 种方案。
选择 A_1A_6\gcd 为 1。
选择 A_2A_4\gcd 为 2。
选择 A_3A_4\gcd 为 2。