Hints: Christmas Tree Decoration

Start with the easier subproblem: for a fixed permutation $p$, how can we check if it is fair?

Let

$$ S = \sum_{i=0}^{n} a_i, \quad k = \left\lfloor \frac{S}{n} \right\rfloor, \quad r = S \bmod n. $$

In any order, the first $k$ full rounds contain exactly $k$ turns for every person, and then only the first $r$ people in $p$ get one extra turn.

Answer to Hint 1: During the first $k$ turns of person $i$, they need $k$ decorations total from boxes $i$ and $0$.

So person $i$ has a deficit

$$ d_i = \max(0,\; k - a_i), $$

and box $0$ must pay this deficit. If

$$ \sum_{i=1}^{n} d_i > a_0, $$

then even the first $k$ rounds are impossible.

Assume it is possible, and spend these deficits from box $0$ first.

After paying deficits for the first $k$ rounds, define leftovers:

$$ b_i = a_i - (k - d_i) = \max(0,\; a_i - k), \qquad b_0 = a_0 - \sum d_i. $$

What must be true about $b_i$ for $i \ge 1$?

Answer to Hint 3: Each person can appear at most once in the extra phase (the next incomplete round), so each personal box can contribute at most one extra decoration:

$$ b_i \le 1 \quad \text{for all } i \ge 1. $$

If some $b_i > 1$, the permutation is impossible (that box cannot be fully emptied).

Now focus on the extra phase of length $r$:

• only positions $p_1, p_2, \dots, p_r$ get one more turn;
• each such person needs one decoration from box $0$ or their own leftover box.

Given that each $b_i \in \{0,1\}$, what does this imply about which indices must appear in the first $r$ positions?

Answer to Hint 5: If $b_i = 1$ but person $i$ is not in the first $r$ positions, that decoration can never be taken (person $i$ never gets an extra turn). So this is invalid.

Therefore, for a fixed permutation:

all indices with $b_i = 1$ must lie in the prefix $p_1 \dots p_r$.

With the earlier conditions (deficits feasible and b_i \le 1), this is also sufficient.

Now switch from checking one permutation to counting all fair permutations.

Let:

• $z =$ number of indices $i \in [1,n]$ with $b_i = 0$,
• $o = n - z =$ number of indices with $b_i = 1$.

Since

$$ r = S \bmod n = b_0 + \sum_{i=1}^{n} b_i = b_0 + o, $$

the first $r$ positions must contain:

• all $o$ ones, and
• exactly $b_0$ zeros.

Answer to Hint 7: First ensure global feasibility:

• $\sum d_i \le a_0$,
• all $b_i \le 1$,
• $b_0 \le z$ (we need at least $b_0$ zero-indices to place in the first $r$).

Then count permutations:

1. choose which $b_0$ zero-indices go to the first $r$: $\binom{z}{b_0}$;
2. permute the first $r$ positions: $r!$;
3. permute the remaining $n-r = z-b_0$ positions: $(z-b_0)!$.

So

$$ \text{ans} = \binom{z}{b_0} \cdot r! \cdot (z-b_0)! = \frac{z! \cdot (n - z + b_0)!}{b_0!}. $$

Compute factorials up to $50$ once. For division by $b_0!$, use modular inverse:

$$ \text{ans} = z! \cdot (n-z+b_0)! \cdot (b_0!)^{-1} \pmod{998244353}. $$

Complexity is $O(n)$ per test case.