Tasty Arrays - Repovive Premier Round 5 | Repovive

13D. Tasty Arrays

2000 pts1s256 MB

An array is called edible if all of the following conditions hold:

its length is at least $n$ ;
every element is one of $0$ , $1$ , and $2$ ;
its first and last elements are nonzero.

The tastiness of an edible array is the number of maximal contiguous blocks consisting only of zeros.

Hamid chooses an edible array of length exactly $n$ uniformly at random among all possible edible arrays of length $n$ . Then he changes the array $k$ times.

Assume the current edible array is $a$ and its length is $L$ . To construct the next array, first add one $0$ to the beginning of $a$ and one $0$ to the end of $a$ . More formally, define $x_0 = 0$ , $x_{L+1} = 0$ , and $x_i = a_i$ for $1 \le i \le L$ .

The new array $b$ has length $L+1$ , and for each $1 \le i \le L+1$ :

b_i = (x_{i-1} + x_i)^2 \bmod 3.

The new array is also edible.

Find the expected value of the sum of tastiness values of all $k+1$ edible arrays Hamid sees, including the initial array.

Output the answer modulo $998244353$ . More precisely, if the expected value is equal to $\frac{P}{Q}$ , output $P \cdot Q^{-1} \bmod 998244353$ .

Constraints

$1 \le t \le 10^5$
$2 \le n \le 10^9$
$1 \le k \le 10^9$

Input

t

\left. \begin{array}{l} n \quad k \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{ans} \end{array} \right\} \times t

Samples

Input

Case 1

2 1

Case 2

3 1

Case 3

4 2

Case 4

5 3

Case 5

6 100

Explanation

Case 1

There are four possible initial arrays. The initial tastiness is always $0$ . After one change, exactly two of them have one zero block, so the expected sum is $\frac{1}{2}$ .

Case 2

The expected tastiness of the initial array is $\frac{1}{3}$ , and the expected tastiness after the change is $\frac{1}{2}$ . Their sum is $\frac{5}{6}$ .

Case 3

For the three arrays Hamid sees, the expected tastiness values are $\frac{5}{9}$ , $\frac{7}{9}$ , and $\frac{1}{6}$ . The total is $\frac{3}{2}$ .

Case 4

The expected total tastiness of the four arrays is $\frac{113}{54}$ .

Case 5

After enough changes, all later arrays have tastiness $0$ . For this case, the expected total tastiness is $\frac{8}{3}$ .

Output

Case 1

499122177

Case 2

831870295

Case 3

499122178

Case 4

203346074

Case 5

665496238

Input

Explanation

Case 1

There are four possible initial arrays. The initial tastiness is always $0$ . After one change, exactly two of them have one zero block, so the expected sum is $\frac{1}{2}$ .

Case 2

The expected tastiness of the initial array is $\frac{1}{3}$ , and the expected tastiness after the change is $\frac{1}{2}$ . Their sum is $\frac{5}{6}$ .

Case 3

For the three arrays Hamid sees, the expected tastiness values are $\frac{5}{9}$ , $\frac{7}{9}$ , and $\frac{1}{6}$ . The total is $\frac{3}{2}$ .

Case 4

The expected total tastiness of the four arrays is $\frac{113}{54}$ .

Case 5

After enough changes, all later arrays have tastiness $0$ . For this case, the expected total tastiness is $\frac{8}{3}$ .

Output

Input

Explanation

Case 1

There are four possible initial arrays. The initial tastiness is always $0$ . After one change, exactly two of them have one zero block, so the expected sum is $\frac{1}{2}$ .

Case 2

The expected tastiness of the initial array is $\frac{1}{3}$ , and the expected tastiness after the change is $\frac{1}{2}$ . Their sum is $\frac{5}{6}$ .

Case 3

For the three arrays Hamid sees, the expected tastiness values are $\frac{5}{9}$ , $\frac{7}{9}$ , and $\frac{1}{6}$ . The total is $\frac{3}{2}$ .

Case 4

The expected total tastiness of the four arrays is $\frac{113}{54}$ .

Case 5

After enough changes, all later arrays have tastiness $0$ . For this case, the expected total tastiness is $\frac{8}{3}$ .

Output

An array is called edible if all of the following conditions hold:

its length is at least $n$ ;
every element is one of $0$ , $1$ , and $2$ ;
its first and last elements are nonzero.

The tastiness of an edible array is the number of maximal contiguous blocks consisting only of zeros.

Hamid chooses an edible array of length exactly $n$ uniformly at random among all possible edible arrays of length $n$ . Then he changes the array $k$ times.

The new array $b$ has length $L+1$ , and for each $1 \le i \le L+1$ :

b_i = (x_{i-1} + x_i)^2 \bmod 3.

The new array is also edible.

Find the expected value of the sum of tastiness values of all $k+1$ edible arrays Hamid sees, including the initial array.

Output the answer modulo $998244353$ . More precisely, if the expected value is equal to $\frac{P}{Q}$ , output $P \cdot Q^{-1} \bmod 998244353$ .

$1 \le t \le 10^5$
$2 \le n \le 10^9$
$1 \le k \le 10^9$

t

\left. \begin{array}{l} n \quad k \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{ans} \end{array} \right\} \times t