Problem Description

Given a sequence \( a \) of length \( n \), initially \( a_i = i \).

There is a random integer \( x \) within the range \([1, n]\) with probability \( b_i \) of being \( i \).

Next, perform \( k \) operations. Each operation randomly selects two integers \( i, j \) from \([1, n]\) (allowing \( i = j \)), and swaps \( a_i \) and \( a_j \) (if \( i = j \), do nothing). You need to find the probability that \( x \) is at position \( i \) after all operations, for all \( 1 \leq i \leq n \). You should output the answer modulo \( 3221225473 \).

We define \( x \) being at position \( i \) as \( a_i = x \).

Input Format

A line containing three integers \( n, k, seed \). The \( b_i \) values are generated using the following code:

#include <cstdio>

typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;

const uint mod = 3221225473u;
const int N = 20000010;

ull seed;

ull getnext() {
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

uint rd(uint l, uint r) {
    return getnext() % (r - l + 1) + l;
}

int n;
ull k;
uint b[N];

int main() {
    scanf("%d%llu%llu", &n, &k, &seed);
    ull sum = 0;
    for (int i = 1; i < n; ++ i) b[i] = rd(2u, mod - 1), (sum += b[i]) %= mod;
    b[n] = mod + 1 - sum;
}

Output Format

Let \( ans_i \) be the probability that \( x \) is at position \( i \) modulo \( 3221225473 \). Output the XOR sum of \( ans_i \times i \).

Sample Input and Output

Sample Input #1

2 9 998244353

Sample Output #1

2684354563

Sample Input #2

7 3 123456789

Sample Output #2

24313281849

Sample Input #3

10 9000000000000000000 1000000000000000000

Sample Output #3

20026214895

Sample Input #4

4 0 123456789

Sample Output #4

12357556560

Notes/Hints

Sample Explanation

For Sample #1:

The \( b \) array is \(\{2134949164, 1086276310\}\), after 9 operations, the probability of \( x \) being in either position is \(\frac{1}{2}\).

For Sample #2:

The \( b \) array is \(\{1863763622, 1043615898, 1055155266, 1556793106, 1763540175, 1239801170, 1141007183\}\).

Data Range

For \( 100\% \) of the data:

• \( 2 \leq n \leq 2 \times 10^7 \), \( 0 \leq k, seed < 2^{64} \).
• \( 1 < b_i < 3221225473 \), \(\sum_{i=1}^n b_i \equiv 1 \pmod{3221225473}\).
• The data guarantees \( 1 < b_n < 3221225473 \) and \( 3221225473 \) is a prime number.

This problem uses subtask testing.

见题面 Input 部分

见题面 Output 部分