/ 
Time Limit: 8 sec / Memory Limit: 2048 MiB
配点 : 100 点
？？？？「2024 年当時の日本では，nim 積の実装についてはよく知られていたようであるし，ハッシュ解法等問題文に直接現れない nimber の利用もしばしば見られたようであるが，数え上げ問題は \mathbb{F} _ {998244353} で行うのが主流であり，この史料のように組合せ的対象に付ける重みとして \mathbb{F} _ {2^{64}} が選択された出題はほとんど見られなかった」
問題文
非負整数 n, m に対し，n 頂点 m 辺のラベル付き単純二部グラフの個数を B(n, m) とする (ラベル付きとは，n 個の頂点が区別されるということ)．
非負整数 N と，A \in \mathbb{F}_{2^{64}} が与えられる．各 n = 0, 1, \ldots, N に対し，g_n = \displaystyle\sum _ {m\ge0} B(n, m) A^m を求めよ．
この問題の入出力では，\mathbb{F}_{2^{64}} の元を 0 以上 2^{64} 未満の nimber によって表す．すなわち g_n は，B(n, m) が奇数であるような m に対する，m 個の A の nim 積の，総 XOR である．
制約
- 0 \le N \le 10^6．
- A \in \mathbb{F}_{2^{64}}．
入力
入力は以下の形式で標準入力から与えられる．A は nimber として表される．
N A
出力
答えを以下の形式で出力せよ．g_0, g_1, \ldots, g_N を nimber として表すこと．
g_0 g_1 \cdots g_N
入力例 1
5 8
出力例 1
1 1 9 4 6 12
n \le 5 の範囲で B(n, m) が奇数であるのは (n, m) = (0, 0), (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 2), (4, 4), (5, 0), (5, 2) のときであるから，
- g_0 = A^0
- g_1 = A^0
- g_2 = A^0 + A^1
- g_3 = A^0 + A^1 + A^2
- g_4 = A^0 + A^2 + A^4
- g_5 = A^0 + A^2
となる (これらは \mathbb{F}_{2^{64}} における演算であることに注意せよ)．
A^0, A^1, A^2, A^3, A^4 を表す nimber は，それぞれ 1, 8, 13, 14, 10 となる．
入力例 2
16 18446744073709551615
出力例 2
1 1 18446744073709551614 7156334549604198409 5893837254661243073 11290409524105353206 1851073793877042652 6387559487065781530 10238440391911562788 4437985372483032842 7848075886096899333 1584478287860827173 12600881811381958477 3270981160664397218 17529507309351360274 100266085651560874 1725589564589995945