P3791 Ordinary Math Problem

One day, zzq had no problems to set. So he casually wrote an expression to compute $\sum_{i=0}^n \sum_{j=0}^m i \operatorname{xor} j \operatorname{xor} x$, where $\operatorname{xor}$ denotes bitwise XOR. zzy thought this was easy, so he casually added a function: $\sum_{i=0}^n \sum_{j=0}^m d(i \operatorname{xor} j \operatorname{xor} x)$, where $\operatorname{xor}$ denotes bitwise XOR and $d(x)$ denotes the number of divisors of $x$. **Note that $d(0) = 0$.** Now zzq could not solve it, so he wrote a brute-force generator to produce testdata and threw this problem to you.

Given three integers $n, m, x$, compute $\sum_{i=0}^n \sum_{j=0}^m d(i \operatorname{xor} j \operatorname{xor} x)$, where $\operatorname{xor}$ denotes bitwise XOR and $d(x)$ denotes the number of divisors of $x$. Since the answer can be large, output the result modulo $998244353$.

One line with three integers $n, m, x$.

Output the answer modulo $998244353$.

For $20\%$ of the testdata, $n, m, x \leq 2000$. For $50\%$ of the testdata, $n, m, x \leq 10^6$. For $80\%$ of the testdata, $n, m, x \leq 10^8$. For $100\%$ of the testdata, $1 \leq n, m, x \leq 10^{10}$. Translated by ChatGPT 5