题目背景
一天 zzq 没有题可以出了。于是他随便写了一个式子,求∑i=0n∑j=0mixorjxorx,其中 xor 表示异或。
zzy 一看,这不是水题吗,就随便加了一个函数:∑i=0n∑j=0md(ixorjxorx),其中 xor 表示异或,d(x) 表示 x 的约数个数。注意 d(0)=0。
现在 zzq 不会做了,只好写了一个暴力造了数据,然后把这道题丢给了你。
题目描述
输入三个数 n,m,x,要求计算 ∑i=0n∑j=0md(ixorjxorx),其中 xor 表示二进制下的异或,d(x) 表示 x 的约数个数。
由于答案比较大,要求输出答案模 998244353 后的结果。
输入格式
一行三个数 n,m,x。
输出格式
输出答案模 998244353 后的结果。
提示
对于 20% 的数据,n,m,x≤2000。
对于 50% 的数据,n,m,x≤106。
对于 80% 的数据,n,m,x≤108。
对于 100% 的数据,1≤n,m,x≤1010。