P8944 The Da Vinci Code
题目背景
> 圣杯在罗斯琳教堂下静待。
> 大师杰作掩映中相拥入眠。
> 剑刃圣杯守护着她的门宅。
> 星空下她可安息无碍。
好的题目不需要花里胡哨的背景。
题目描述
给定一个长度为 $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$：
```cpp
#include
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 > 17;
seed ^= seed
输出格式
设 $ans_i$ 表示 $x$ 在位置 $i$ 上的概率模 $3221225473$，则输出 $ans_i\times i$ 的异或和。
说明/提示
#### 【样例解释】
对于样例 #1：
$b$ 数组为 $\{2134949164 ,1086276310\}$，操作 $9$ 次后 $x$ 在两个位置的概率均为 $\dfrac12$。
对于样例 #2：
$b$ 数组为 $\{1863763622,1043615898,1055155266,1556793106,1763540175,1239801170,1141007183\}$。
#### 【数据范围】
对于 $100\%$ 的数据：
* $2\leq n\leq2\times10^7$，$0\leq k,seed