普通数学题

题目背景

一天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}$。