P8594 "KDOI-02" Revenge for a Grudge

**Due to the OI contest format, subtasks are disabled for this problem. Some incorrect solutions may get high scores. Subtasks will be enabled after the contest.** "Have you heard about that incident? May they rest in peace." "Huh? Look, what is that ring-shaped building ahead?" "Let me compare it... Aha! This is their lair!" "Destroy it, and avenge our fallen comrades!!!" Dead cosmic rays point at fragile civilizations, ready to unleash their thunderous roar.

The aliens' space station has a ring-shaped structure. However, since the two ends of the ring are not connected, it can be approximated as a $2\times n$ planar grid. Now, our ships have $n$ different types of ray weapons, each affecting a $1\times x$ rectangle ($x$ is a positive integer). Also, the weapon can be rotated $90^\circ$ clockwise or counterclockwise. The ray is extremely powerful: a single shot can annihilate everything within the affected area. However, if any part of the ray's affected area falls outside the target, it will keep extending to the end of the universe, greedily devouring everything along its path. The commander of course does not want to endanger innocent civilizations. He wants to know: among these $n$ weapons, if we choose $k$ types, how many different ways are there to destroy the aircraft. **[Formal statement]** You have infinitely many rectangles of size $1\times x$ ($x$ can be any positive integer) and a $2\times n$ grid. Find the number of ways to select exactly $k$ rectangles (you may select identical rectangles) to tile the entire grid **without overlap and without gaps**. Rectangles may be rotated.

Read input from standard input. The input contains one line with two positive integers $n,k$.

Write output to standard output. Output one line with one positive integer, the number of tiling ways modulo $998244353$.

**** **[Sample explanation]** + **Sample 1 explanation:** There are $8$ solutions as shown in the figure below.  *** **[Constraints]** For $100\%$ of the testdata, $1\le n\le 2\times 10^7$, $1\le k\le 5000$. | Test Point ID | Score | $n$ | $k$ | | :----------: | :----------: | :----------: | :----------: | |$1\sim 5$| $2$ | $\leq5$ | $\leq10$ | |$6\sim 10$| $2$ | $\leq1000$ | $=2n$ | |$11\sim 15$| $2$ | $\leq10^6$ | $\leq3$ | |$16\sim 20$| $4$ | $\leq1000$ | $\leq2n$ | |$21\sim 25$| $4$ | $\leq2\times10^7$ | $\leq100$ | |$26\sim 30$| $4$ | $\leq10^6$ | $\leq5000$ | |$31\sim 40$| $1$ | $\leq2\times10^7$ | $\leq5000$ | Note: the Score column is the score of a single test point. Translated by ChatGPT 5