Problem Background

Monsters love factors, so he decided to create a problem about them.

Problem Description

As we know, the standard factorization of \( i \) is: \( \prod\limits_{j=1}^{k_i} p_{i,j}^{c_{i,j}} \).

Given a sequence \( a \) of length \( n \).

Define \( f(x) = \sum\limits_{d|x} \left( a_{\frac{x}{d}} \times \prod\limits_{i=1}^{k_d} C_{c_{d,i}+m}^{m} \right) \), where \( m \) is a given constant. You are required to compute \( f(1), f(2), f(3), \cdots, f(n) \).

Since Monsters dislike large numbers, he wants you to output the answers modulo \( 998244353 \).

Additionally, to avoid excessive input/output, this problem uses a random number generator for data, and you only need to output the XOR sum of all answers.

If you are unfamiliar with \( C \), \( C_n^m = \dfrac{n!}{m!(n-m)!} \), where \( ! \) denotes factorial.

Input Format

The input consists of a single line.

The first line contains three non-negative integers \( n, m, seed \).

You need to call the data generator (randomdigit) \( n \) times within your program to obtain \( a \).

Output Format

The output consists of a single line containing one integer, which is the XOR sum of all \( f(x) \).

Sample Input and Output

Sample Input #1

3 0 12345678

Sample Output #1

175092810

Sample Input #2

114514 100000 1919810

Sample Output #2

212218651

Sample Input #3

9919810 2 12121121

Sample Output #3

204065242

Notes

Data Generator

C/C++:

#define uint unsigned int
uint seed;
inline uint randomdigit(){
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

Pascal:

var seed: dword;
function randomdigit: dword;
begin
    seed := seed xor (seed shl 13);
    seed := seed xor (seed shr 17);
    seed := seed xor (seed shl 5);
    randomdigit := seed;
end;

Python3:

seed = 0 # please input seed
mod = 1 << 32
def randomdigit():
    global seed
    seed ^= (seed << 13) % mod
    seed ^= (seed >> 17) % mod
    seed ^= (seed << 5) % mod
    return seed

Sample Explanation

The sequence \( a \) is \( 506005380, 3857352168, 531380003 \).

The values of \( f(1), f(2), f(3) \) modulo \( 998244353 \) are \( 506005380, 370380136, 39141030 \).

Data Range

For \( 100\% \) of the data, \( 0 \le m \le 10^5, 1 \le n \le 10^7, 0 \le a_1, a_2, \cdots, a_n, seed < 2^{32} \).

• Subtask \( 1 \) (30% of the data): \( n \le 10^6, m \le 10^5 \).

Within this Subtask:

• 10% of the data satisfy \( m = 0 \).

• Another 10% of the data satisfy \( n \le 100 \).

• Subtask \( 2 \) (70% of the data): \( n \le 10^7, m \le 3 \).

Hints

Please be mindful of the space limit and the impact of constant factors on program efficiency.

见题面 Input 部分

见题面 Output 部分