Hamza has created the following sorting algorithm:
To sort an array, he calls sort(1).
He doesn't know how the array ends up after running the algorithm (sorted?), so he's asking for your help.
The first line contains a single integer $n$ $(1 <= n <= 10^5)$ — the length of the array.
The second line contains $n$ space-separated integers denoting the array $a$ $(0 <= a_i <= 10^9)$.
Print the final array after running the algorithm on it.
*For simplicity, in this portion of the problem, we'll consider the least significant $3$ bits.*
The $a n d$ between two integers $x$ and $y$ is the bitwise anding between the two numbers:
$1$ $a n d$ $0$ $=$ $0$ $a n d$ $1$ $=$ $0$ $a n d$ $0$ $=$ $0$
$1$ $a n d$ $1$ $=$ $1$
For example:
$7_{10}$ $a n d$ $5_{10}$ $=$ $5_{10}$
$7_{10}$ $=$ $111_2$, $5_{10}$ $=$ $101_2$
$111_2$ $a n d$ $101_2$ $=$ $101_2$ = $5_{10}$
The not of an integer $x$ is taking the complement of the integer (flipping it bits):
$n o t$ $0$ $=$ $1$
$n o t$ $1$ $=$ $0$
For example:
$n o t$ $5_{10}$ $=$ $2_{10}$
Explanation:
$5_{10}$ $=$ $101_2$
$n o t$ $101_2$ = $010_2$ = $2_{10}$
## Input
The first line contains a single integer $n$ $(1 <= n <= 10^5)$ — the length of the array.The second line contains $n$ space-separated integers denoting the array $a$ $(0 <= a_i <= 10^9)$.
## Output
Print the final array after running the algorithm on it.
[samples]
## Note
*For simplicity, in this portion of the problem, we'll consider the least significant $3$ bits.*The $a n d$ between two integers $x$ and $y$ is the bitwise anding between the two numbers: $1$ $a n d$ $0$ $=$ $0$ $a n d$ $1$ $=$ $0$ $a n d$ $0$ $=$ $0$$1$ $a n d$ $1$ $=$ $1$For example:$7_(10)$ $a n d$ $5_(10)$ $=$ $5_(10)$$7_(10)$ $=$ $111_2$, $5_(10)$ $=$ $101_2$$111_2$ $a n d$ $101_2$ $=$ $101_2$ = $5_(10)$The not of an integer $x$ is taking the complement of the integer (flipping it bits):$n o t$ $0$ $=$ $1$$n o t$ $1$ $=$ $0$For example:$n o t$ $5_(10)$ $=$ $2_(10)$Explanation:$5_(10)$ $=$ $101_2$$n o t$ $101_2$ = $010_2$ = $2_(10)$
**Definitions**
Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n < 10^{105} $.
Let $ D = \{0, 2, 5, 6, 8, 9\} $ be the set of visible digits.
Define a mapping $ f: D \to D $ for 180-degree rotation:
$$
f(0) = 0, \quad f(2) = 5, \quad f(5) = 2, \quad f(6) = 9, \quad f(8) = 8, \quad f(9) = 6
$$
Let $ A = (a_1, a_2, \dots, a_n) \in D^n $ be a digit sequence (allowing leading zeros).
Let $ B = (b_1, b_2, \dots, b_n) $ be the rotated sequence, where $ b_i = f(a_{n+1-i}) $.
We require $ A = B $, i.e., $ a_i = f(a_{n+1-i}) $ for all $ i \in \{1, \dots, n\} $.
**Constraints**
- $ n \in \mathbb{Z}^+ $, $ 1 \leq n < 10^{105} $
- Each $ a_i \in D $
**Objective**
Count the number of sequences $ A \in D^n $ such that $ a_i = f(a_{n+1-i}) $ for all $ i = 1, \dots, n $, modulo $ 998244353 $.
Let $ m = \left\lceil \frac{n}{2} \right\rceil $.
For each position $ i \in \{1, \dots, m\} $, the pair $ (a_i, a_{n+1-i}) $ must satisfy $ a_i = f(a_{n+1-i}) $.
- If $ n $ is odd, the middle digit $ a_{(n+1)/2} $ must satisfy $ a_i = f(a_i) $, i.e., fixed points of $ f $: $ \{0, 8\} $ (2 choices).
- For each symmetric pair $ (i, n+1-i) $ with $ i < n+1-i $, the number of valid pairs $ (x, y) \in D \times D $ such that $ x = f(y) $ and $ y = f(x) $ is the number of self-paired digits under $ f $:
Valid pairs: $ (0,0), (2,5), (5,2), (6,9), (9,6), (8,8) $ → 6 valid unordered pairs, but since $ x = f(y) $ uniquely determines $ y $, we count the number of $ x \in D $ such that $ f(f(x)) = x $ and $ x = f(y) $ for some $ y $.
Actually, each valid $ x \in D $ has a unique $ y = f(x) $, and the constraint $ a_i = f(a_{n+1-i}) $ means we choose $ a_i \in D $, then $ a_{n+1-i} $ is forced to $ f(a_i) $.
But for the pair to be consistent, we require $ a_{n+1-i} = f(a_i) $, and then $ a_i = f(a_{n+1-i}) = f(f(a_i)) $. So we require $ f(f(a_i)) = a_i $.
Check:
- $ f(f(0)) = f(0) = 0 $ ✓
- $ f(f(2)) = f(5) = 2 $ ✓
- $ f(f(5)) = f(2) = 5 $ ✓
- $ f(f(6)) = f(9) = 6 $ ✓
- $ f(f(8)) = f(8) = 8 $ ✓
- $ f(f(9)) = f(6) = 9 $ ✓
So **every** $ x \in D $ satisfies $ f(f(x)) = x $. Therefore, for each symmetric pair, we may choose $ a_i \in D $ arbitrarily, and then $ a_{n+1-i} = f(a_i) $ is determined.
Thus, for each of the $ \left\lfloor \frac{n}{2} \right\rfloor $ symmetric pairs, we have $ |D| = 6 $ choices.
For the center digit (if $ n $ is odd), we need $ a_{\text{mid}} = f(a_{\text{mid}}) $, i.e., fixed points of $ f $: $ \{0, 8\} $ → 2 choices.
Thus, total number of valid sequences:
$$
\begin{cases}
6^{n/2} & \text{if } n \text{ even} \\
6^{(n-1)/2} \cdot 2 & \text{if } n \text{ odd}
\end{cases}
$$
**Answer**
$$
\boxed{
\begin{cases}
6^{n/2} \mod 998244353 & \text{if } n \text{ even} \\
2 \cdot 6^{(n-1)/2} \mod 998244353 & \text{if } n \text{ odd}
\end{cases}
}
$$