Permutation Counting (Hard)

**This is the hard version of the problem. Here $2 \le K < 2 \cdot N$.** You are given $2$ integers, $N$ and $K$. Count the number of permutations $P$ of the integers $[1, N]$ satisfying the following condition: - $(P_i + P_{i + 1}) \mod K \ne 0$ for all $1 \le i < N$ Since the answer may be large, output it modulo $998244353$. ### Input - The first line of input will contain a single integer