Background

After the contest ended, Zhili, Yangmai, Huamao invited Duanyao, and the four became friends from then on.

In fact, not only Duanyao, but also Zhili, Yangmai, and Huamao were once the strongest in the OI community. After getting AK again and again in one Trash Round after another, they got tired, disappeared from the scene, and quit the world of OI.

Today, seeing that Duanyao is still as talented as before, they again think of those times spent with OI... and excitement rises in their hearts.

So they found Junjun, the leader of PFLOI, and asked Junjun to give them a chance to shine again—by holding a contest of their own.

After hearing their stories, Junjun was deeply moved and gladly agreed. The five of them gathered in PFLOI.

But after Yangmai joined PFLOI, making problems randomly being too naughty, Junjun was not happy, so:

Problem Description

There are $n$ operations. In each operation, one of the following events happens with equal probability:

1. Add $a_i$ into the team. After the operation, $a_i$ becomes a member.
2. Kick $a_i$ out of the team.
3. Set $a_i$ as an administrator.
4. Set $a_i$ as a member.

Note:

• Initially, nobody is in the team.
• If $a_i$ is not in the team, then operations 2, 3, 4 have no effect.
• If $a_i$ is a member, then operations 1 and 4 have no effect.
• If $a_i$ is an administrator, then operations 1, 2, 3 have no effect.

Finally, output the expected number of administrators in the team, modulo $998244353$.

Input Format

The first line contains an integer $\text{type}$.
If $\text{type}$ is $1$, use the first input method; otherwise, use the second input method.

First input method:

The first line contains a positive integer $n$.
The second line contains $n$ integers representing the array $a$.

Second input method:

A single line contains four integers $n,a_0,p,q$.

Note: In the second input method, you need to compute the array $a$, which satisfies $a_i=(a_{i-1}\times p+p)\bmod q+ 1$ $(i \geq 1)$.

Output Format

Output one integer representing the expected number of administrators in the team, modulo $998244353$.

1
6
1 1 2 1 2 1

760381441

2
11 4 5 14

686292993

Hint

This problem uses bundled tests.

For all testdata, $1\le n\le 10^{18}$.

Translated by ChatGPT 5