| VII UnBalloon Contest Mirror |
|---|
| Finished |
The secret organization UnBalloon has $$$N$$$ agents, numbered from $$$1$$$ to $$$N$$$. Using a secret algorithm, the organization calculated, for each of them, their value as a human being, so they could order the agents by this value (no two agents have the same value). From this, the list $$$L$$$ was created, where $$$L_i$$$ is the number of the $$$i$$$-th most valuable agent.
The organization must form a team of agents for the next mission, which is to infiltrate the Super Ultra Secret Pizza. But for the mission to be successful, the chosen agents must follow a special property. Let $$$S$$$ be the set of numbers of the chosen agents and $$$P$$$ be the set of positions of these agents in the list $$$L$$$. From these sets, we define the polynomials$$$^1$$$ $$$A(x) = \sum_{i \in S} x^i$$$ and $$$B(x) = \sum_{i \in P} x^i$$$. For this team of agents to be successful, it is necessary that $$$S$$$ is not an empty set and that there exists some polynomial $$$C(x)$$$ with all its coefficients being non-negative integers such that $$$A(x) \cdot C(x) = B(x)$$$.
As part of the organization's analysts, you must calculate how many ways there are to form a team of agents that would be successful in the mission. Since this quantity can be very large, calculate the remainder of this quantity when divided by $$$998244353$$$.
$$$^1$$$ A polynomial is a function of the form $$$P(x) = \sum\limits_{i=0}^\infty a_i \cdot x^i$$$ such that the number of non-zero values $$$a_i$$$ is finite. The $$$a_i$$$'s are called coefficients.
The first line of input contains the integer $$$N$$$: the number of agents $$$(1 \leq N \leq 5 \cdot 10 ^3)$$$.
The second line of input contains $$$N$$$ distinct integers: the list $$$L$$$ $$$(1 \leq L_i \leq N)$$$.
Print, on a single line, the remainder when dividing by $$$998244353$$$ of the number of ways to form a team of agents for a successful mission.
11
1
42 1 4 3
6
41 3 2 4
8
101 4 5 3 2 10 9 8 7 6
49
| Name |
|---|


