标题:铺瓷砖
为了让蓝桥杯竞赛更顺利的进行,主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个n*m的矩形,而这次使用的瓷砖比较特别,有两种形状,如【图1.png】所示。在铺放瓷砖时,可以旋转。
主办方想知道,如果使用这两种瓷砖把机房铺满,有多少种方案。
【输入格式】
输入的第一行包含两个整数,分别表示机房两个方向的长度。
【输出格式】
输出一个整数,表示可行的方案数。这个数可能很大,请输出这个数除以65521的余数。
【样例输入1】
4 4
【样例输出1】
2
【样例说明1】
这两种方案如下【图2.png】所示:
【样例输入2】
2 6
【样例输出2】
4
【数据规模与约定】
对于20%的数据,1<=n, m<=5。
对于50%的数据,1<=n<=100,1<=m<=5。
对于100%的数据,1<=n<=10^15,1<=m<=6。
资源约定:
峰值内存消耗 < 512M
CPU消耗 < 5000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。