Problem Background

One day, zzq had no problems to create. So he randomly wrote an expression to calculate $\sum_{i=0}^n \sum_{j=0}^m i \text{ xor } j \text{ xor } x$, where xor denotes the bitwise XOR operation.

zzy saw this and thought it was an easy problem, so he added a function: $\sum_{i=0}^n \sum_{j=0}^m d(i \text{ xor } j \text{ xor } x)$, where xor denotes the bitwise XOR operation, and \( d(x) \) represents the number of divisors of \( x \). Note that \( d(0) = 0 \).

Now, zzq couldn't solve it and had to write a brute-force solution to generate the data, then he threw this problem to you.

Problem Description

Given three numbers \( n \), \( m \), and \( x \), you are required to compute \(\sum_{i=0}^n \sum_{j=0}^m d(i \text{ xor } j \text{ xor } x)\), where xor denotes the bitwise XOR operation in binary, and \( d(x) \) represents the number of divisors of \( x \).

Since the answer can be very large, output the answer modulo 998244353.

Input Format

A single line containing three numbers \( n \), \( m \), and \( x \).

Output Format

Output the answer modulo 998244353.

Sample Input and Output

Sample Input #1

0 2 233

Sample Output #1

14

Sample Input #2

123 234 345

Sample Output #2

205761

Notes

For 20% of the data, \( n, m, x \leq 2000 \).

For 50% of the data, \( n, m, x \leq 10^6 \).

For 80% of the data, \( n, m, x \leq 10^8 \).

For 100% of the data, \( 1 \leq n, m, x \leq 10^{10} \).

见题面 Input 部分

见题面 Output 部分