Given a sequence of integers \(a_1,a_2,...,a_n\); find the number of sets \(S\) satisfying the following conditions:

• \(S \sub \{1, 2, ..., n\}\)
• \(\exist x \in S : a_x \in S\)
• \(\exist y \in S : (\forall x \in S : a_x \ne y)\)

Since the result can be rather large, you should output it modulo \(998244353\).

Input

The input contains multiple test cases. Each test case is presented in two lines as below:

• The first line contains an integer \(n (1 \le n \le 10^5 )\).
• The second line contains \(n\) integers \(a_1,a_2,...,a_n (1 \le |a_i | \le n)\).

The input is terminated by a line with a single integer \(0\) which is not a test case. The sum of n over all test cases does
not exceed \(10^6\)
.

Output

For each test case, write the result on the single line.

Example

3
1 2 3
3
2 3 1
0

0
6