410445: GYM104022 C Lucky Sequence

A number sequence $$$[a_1, a_2, \ldots, a_n]$$$ is lucky if and only if the following requirements are fulfilled.

• Each element $$$a_i$$$ in the sequence is a non-negative integer such that $$$0 \leq \frac{a_i}{i} < \frac{\sqrt{5} + 1}{2}$$$;
• For any two elements $$$a_i$$$ and $$$a_j$$$ $$$(i \neq j)$$$ in the sequence, $$$a_i \neq 0$$$ and $$$a_j \neq 0$$$ imply that $$$a_i \neq a_j$$$.

Your task is to figure out how many number sequences of length $$$n$$$ are lucky and report the number modulo $$$998\,244\,353$$$.

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, indicating the number of test cases.

Then follow $$$T$$$ test cases. For each test case:

The only line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, indicating the length of the sequence.

For each test case, output an integer in one line, representing the number of lucky sequences of length $$$n$$$ modulo $$$998\,244\,353$$$.

5
1
2
3
4
5

2
7
27
141
919

For $$$n = 2$$$, there are $$$7$$$ lucky sequences: $$$[0, 0]$$$, $$$[0, 1]$$$, $$$[0, 2]$$$, $$$[0, 3]$$$, $$$[1, 0]$$$, $$$[1, 2]$$$ and $$$[1, 3]$$$.