Expected Number of Administrators

You are given a team that is initially empty. There will be n operations. In each operation, an integer a_i is given and one of the following 4 events occurs with equal probability:

• Add: If a_i is not in the team then add a_i as a member.
• Kick: If a_i is a member then remove a_i from the team. (If a_i is not in the team, do nothing.)
• Promote: If a_i is a member then change his status to administrator. (If a_i is not in the team, do nothing.)
• Set Member: If a_i is in the team then set his status to member. (If he is already a member or not in the team, do nothing.)

Note:

• The team starts empty.
• If a_i is not in the team, then the Kick, Promote, and Set Member operations have no effect.
• If a_i is already a member, then the Add and Set Member operations have no effect.
• If a_i is already an administrator, then the Add, Kick, and Promote operations have no effect.

After performing all n operations these events occur independently (each operation chooses one of the four events uniformly at random). Compute the expected number of administrators in the team. Since this expectation is a rational number, output it modulo 998244353.

All formulas should be written in LaTeX. For example, the modulus should be expressed as \(998244353\).

inputFormat

The first line contains an integer \(n\): the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) represents the identifier for the operation.

outputFormat

Output a single integer: the expected number of administrators in the team modulo \(998244353\).

sample

1
100

0