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