P3990 [SHOI2013] Super Jumping Knight

Given an $n$-row by $m$-column board, a knight wants to jump from the top-left corner to the bottom-right corner. At each step, it jumps to the right by an odd number of columns and lands in the same row or an adjacent row. During the jump, the knight must not leave the board. For example, when $n = 3$, $m = 10$, the figure below shows a valid sequence of jumps.  Find the number of different jump sequences modulo $30\,011$.

A single line containing two positive integers $n$, $m$, representing the size of the board.

Output a single line containing one integer, the number of jump sequences modulo $30\,011$.

- For $10\%$ of the testdata, $1 \leq n \leq 10$, $2 \leq m \leq 10$. - For $50\%$ of the testdata, $1 \leq n \leq 10$, $2 \leq m \leq 10^5$. - For $80\%$ of the testdata, $1 \leq n \leq 10$, $2 \leq m \leq 10^9$. - For $100\%$ of the testdata, $1 \leq n \leq 50$, $2 \leq m \leq 10^9$. Translated by ChatGPT 5