Background

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.

Problem Description

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$.

Input Format

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

Output Format

Output the answer modulo $998244353$.

0 2 233

14

123 234 345

205761

Hint

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