I-Random_2025牛客国庆集训派对day7

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Walk Alone has a strange random number generator, the pseudocode of which is as follows:

uintk rand(uintk x, int A[]) {
  for (int i = 0; i < n; ++i) {
    if (A[i] >= 0) x ^= x << A[i];
    else x ^= x >> -A[i];
  }
  return x;
}

Here ' $\texttt{uintk}$ ' denotes the type of unsigned integers with $k$ binary bits, and ' $\texttt{n}$ ' denotes the size of array $A$ . You can use ' $\texttt{std::bitset}$ ' in C++ to implement all operations involving ' $\texttt{uintk}$ '.
Now Walk Alone is given an array $A$ and an integer $k$ . He found that for any integer $x\ (0\le x<2^k)$ , there exists a positive integer $T$ such that $\text{rand}_T(x,A)=x$ , where
$\text{rand}_T(x,A)=\begin{cases}<br /> \text{rand}(\text{rand}_{T-1}(x,A),A), & T\ge 1 \\<br /> x, & T=0<br />\end{cases}$
Let $f(x)=\min\{T>0\mid \text{rand}_T(x,A)=x\}$ . Walk Alone wants to know the expected value of $f(x)$ modulo $998\,244\,353$ if $x$ is chosen from $\{0,1,\dots,2^k-1\}$ with equal probability.
It can be shown that the answer can always be expressed as an irreducible fraction $x/y$ , where $x$ and $y$ are integers and $y \not\equiv 0 \pmod{998\,244\,353}$ . Output such an integer $a$ that $0 \leq a < 998\,244\,353$ and $a\cdot y \equiv x \pmod{998\,244\,353}$ .

输入描述:

The first line contains two integers  and , the size of array  and the length of type '' respectively.
The second line contains  integers, the -th of which is .

输出描述:

Print the expected number of  modulo  in one line.

示例1

输入

复制

1 2
1

输出

复制

499122178

示例2

输入

复制

0 32

输出

复制

示例3

输入

复制

3 5
2 3 -4

输出

复制

623902730

备注:

In the first example, when , the values of function  and  are as follows:
    .
    .
    .
    .
Hence the expected value of  is , which is congruent to  modulo .