Перестановка \(p\) длины \(n\) называется почти идеальной, если для всех целых \(1 \leq i \leq n\), выполняется условие \(\lvert p_i - p^{-1}_i \rvert \le 1\), где \(p^{-1}\) является перестановкой обратной \(p\) (т.е. \(p^{-1}_{k_1} = k_2\) тогда и только тогда, когда \(p_{k_2} = k_1\)).
Посчитайте количество почти идеальных перестановок длины \(n\) по модулю \(998244353\).
Выходные данные
Для каждого набора входных данных выведите единственное число — количество почти идеальных перестановок длины \(n\) по модулю \(998244353\).
Примечание
Для \(n = 2\), обе перестановки \([1, 2]\) и \([2, 1]\) являются почти идеальными.
Для \(n = 3\), есть только \(6\) перестановок. Взглянув на все из них, мы получаем:
- \([1, 2, 3]\) является почти идеальной перестановкой.
- \([1, 3, 2]\) является почти идеальной перестановкой.
- \([2, 1, 3]\) является почти идеальной перестановкой.
- \([2, 3, 1]\) НЕ является почти идеальной перестановкой (\(\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2\)).
- \([3, 1, 2]\) НЕ является почти идеальной перестановкой (\(\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2\)).
- \([3, 2, 1]\) является почти идеальной перестановкой.
Поэтому мы получаем \(4\) почти идеальные перестановки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
3
50
|
2
4
830690567
|