Tiling a Grid

Time limit2sMemory limit128 MB

Summary

Count the ways to fully tile an N by M grid (N, M up to 14) with 2x1 dominoes, modulo 9901.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

There is a rectangular grid with N rows and M columns. Fill the entire grid with 2x1 dominoes without leaving any empty cells. A domino may also be rotated and placed as 1x2.

Given N and M, compute the number of ways to tile the grid with dominoes.

Input

The first line contains two integers N and M.

Output

Print the number of ways to tile the grid without empty cells, modulo 9901.

Constraints

1 ≤ N, M ≤ 14

Examples2

Example 1
Input
```
3 6
```
Expected output
```
41
```
Example 2
Input
```
5 5
```
Expected output
```
0
```