There is an $n \times m$ chessboard. A knight wants to jump from the top-left corner to the bottom-right corner. In each step, it must jump an odd number of columns to the right, and it must land in the same row or an adjacent row. During the jumps, the knight cannot leave the chessboard. For example, when $n = 3$ and $m = 10$, the following figure shows one possible sequence of jumps.

Calculate the number of ways to reach the destination, modulo $30011$.

Input

The input consists of a single line containing two positive integers $n$ and $m$, representing the dimensions of the chessboard.

Output

Output a single line containing one integer, the number of ways modulo $30011$.

Examples

Input 1

3 5

Output 1

10

Constraints

For $10\%$ of the data, $1 \le n \le 10$, $2 \le m \le 10$; For $50\%$ of the data, $1 \le n \le 10$, $2 \le m \le 10^5$; For $80\%$ of the data, $1 \le n \le 10$, $2 \le m \le 10^9$; For $100\%$ of the data, $1 \le n \le 50$, $2 \le m \le 10^9$.