给定一个长度为 n 的数列 a，初始情况下 a_i=i。

另有一个取值在 [1,n] 内的随机的整数 x，它取 i 的概率为 b_i。

接下来进行 k 次操作，每次均匀随机地选两个 [1,n] 中的整数 i,j（允许 i=j），交换 a_i,a_j 的值（如果 i=j 则什么也不干）。问最后 x 在位置 i 上的概率，你需要对所有 1\leq i\leq n 求出答案。你需要输出答案模 3221225473 的值。

我们定义 x 在位置 i 上指 a_i=x。

一行三个整数 n,k,seed。接下来使用如下代码生成 b_i：

#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;
}

设 ans_i 表示 x 在位置 i 上的概率模 3221225473，则输出 ans_i\times i 的异或和。

比如概率为3/5，那么即为3×inv(5)。

【样例解释】

对于样例 #1：

b 数组为 {2134949164 ,1086276310}，操作 9 次后 x 在两个位置的概率均为 \dfrac12。

对于样例 #2：

b 数组为 {1863763622,1043615898,1055155266,1556793106,1763540175,1239801170,1141007183}。

luogu