Марин хочет, чтобы вы посчитали количество красивых перестановок. Красивой перестановкой длины \(n\) называется перестановка, обладающая следующим свойством: \(\) \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, \(\) где \(\gcd\) — это наибольший общий делитель.
Перестановка — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. К примеру, \([2,3,1,5,4]\) является перестановкой, а \([1,2,2]\) — не является (\(2\) встречается в массиве дважды), как и массив \([1,3, 4]\) (\(n=3\), но в массиве присутствует \(4\)).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество красивых перестановок. Так как ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Примечание
В первом наборе существует единственная перестановка \([1]\), но она не является красивой, так как \(\gcd(1 \cdot 1) = 1\).
Во втором наборе существует единственная красивая перестановка \([2, 1]\), так как \(\gcd(1 \cdot 2, 2 \cdot 1) = 2\).