P7431 [THUPC 2017] Little L’s Calculation Problem

You are given a non-negative integer array $\{a_i\}$ of length $n$. Little L defines a magical transform: $$f_k=\left(\sum_{i=1}^na_i^k\right)\bmod 998244353$$ Little L plans to do something interesting with the sequence $f$ generated by this transform, but he is not good at multiplication, so he asks you for help and hopes you can compute $f_{1\dots n}$ as quickly as possible.

The input contains multiple test cases. The first line contains an integer $T$, which indicates the number of test cases. The next $2T$ lines describe the test cases, with every two lines forming one test case. In each test case, the first line contains an integer $n$, which is the length of the array $\{a_i\}$. The next line contains $n$ integers describing the array $\{a_i\}$. It is guaranteed that the input $a_i$ satisfy $0\le a_i\le10^9$. In one test file, it is guaranteed that $\sum n\le 4\times 10^5$.

We do not want you to output too many numbers. Therefore, let $ans=\bigoplus_{i=1}^{n}f_i$, where $\bigoplus$ denotes the **XOR** operation, which can be written as `^` in C++ / Java / Python. For each test case, output one integer per line, representing $ans$.

For $100\%$ of the testdata, $0\le a_i\le10^9$, $1\le n\le 2\times 10^5$, and $\sum n\le 4\times 10^5$. #### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017. Translated by ChatGPT 5