Description

To make the Lanqiao Cup contest run more smoothly, the organizers decided to re-tile the computer lab used for the contest. The lab can be viewed as an $n \times m$ rectangle. The tiles used this time are special and come in two shapes, as shown in Figure 1. During tiling, the tiles may be rotated.

The organizers want to know: if we use these two kinds of tiles to completely cover the lab, how many different tiling方案 (fang'an, plans) are there.

Input Format

The first line contains two integers, representing the lengths of the lab in the two directions.

Output Format

Output one integer, the number of feasible tiling plans. This number may be very large; output the remainder when it is divided by $65521$.

4 4

2

2 6

4

Hint

Sample Explanation

Constraints

For $20\%$ of the testdata, $1 \le n, m \le 5$.

For $50\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 5$.

For $100\%$ of the testdata, $1 \le n \le 10^{15}$, $1 \le m \le 6$.

Time limit: 5 seconds. Memory limit: 512 MB. Lanqiao Cup 2015, the 6th National Final.

Translated by ChatGPT 5