题目描述

为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个 n×m 的矩形，

而这次使用的瓷砖比较特别，有两种形状，如下图所示。在铺放瓷砖时，可以旋转。

主办方想知道，如果使用这两种瓷砖把机房铺满，有多少种方案。

输入描述

输入的第一行包含两个整数，分别表示机房两个方向的长度。

其中，1≤n≤10¹⁵，1≤m≤6。

输出描述

输出一个整数，表示可行的方案数。这个数可能很大，请输出这个数除以 65521 的余数。

输入输出样例

示例 1

输入

4 4

输出

2

样例说明

这两种方案如下图所示：

示例 2

输入

2 6

输出

4