普通数学题
题目背景
一天zzq没有题可以出了。于是他随便写了一个式子,求$\sum_{i=0}^n \sum_{j=0}^m i~xor~j~xor~x$,其中xor表示异或。
zzy一看,这不是水题吗,就随便加了一个函数:$\sum_{i=0}^n \sum_{j=0}^m d(i~xor~j~xor~x)$,其中xor表示异或,d(x)表示x的约数个数。**注意d(0)=0。**
现在zzq不会做了,只好写了一个暴力造了数据,然后把这道题丢给了你。
题目描述
输入三个数n、m、x,要求计算$\sum_{i=0}^n \sum_{j=0}^m d(i~xor~j~xor~x)$,其中xor表示二进制下的异或,d(x)表示x的约数个数。
由于答案比较大,要求输出答案 mod 998244353。
输入输出格式
输入格式
一行三个数n、m、x。
输出格式
输出答案mod 998244353。
输入输出样例
输入样例 #1
0 2 233
输出样例 #1
14
输入样例 #2
123 234 345
输出样例 #2
205761
说明
对于20%的数据,$n,m,x \leq 2000$。
对于50%的数据,$n,m,x \leq 10^6$。
对于80%的数据,$n,m,x \leq 10^8$。
对于100%的数据,$1 \leq n,m,x \leq 10^{10}$。