← 返回题目列表

Codeforces · 1178/C

C. 瓷砖

中文机器翻译题面 查看原题

鲍勃正在装饰他的厨房,更准确地说,是地板。他已经找到了他将使用的瓷砖的主要候选者。它们具有简单的外形——一个方形瓷砖,对角线分成白色和黑色部分,如下图所示。

这块瓷砖的尺寸非常适合这个厨房,因为他将需要 $$$w \times h$$$ 瓷砖,没有任何废料。也就是说,厨房的宽度是$$$w$$$瓷砖,高度是$$$h$$$瓷砖。由于每块瓷砖都可以以四种方式之一旋转,因此他仍然需要决定如何准确地铺地板。他想要满足一个美学标准:两个相邻的图块不得在边缘上共享同一种颜色,即其中一个图块的共享边框必须为白色,第二个图块必须为黑色。

左图显示了 $$$3 \times 2$$$ 厨房的一张有效瓷砖。右图显示了无效的排列,因为底部的两个瓷砖与其白色部分接触。

找出可能的平铺数量。由于这个数字可能很大,因此输出除以 $$$998244353$$$(质数)后的余数。

输入

唯一的一行包含两个空格分隔的整数 $$$w$$$, $$$h$$$ ($$$1 \leq w,h \leq 1\,000$$$) - 厨房的宽度和高度,以瓷砖为单位测量。

输出

输出单个整数 $$$n$$$ — 平铺数量除以 $$$998244353$$$ 后的余数。

示例

输入 #1

2 2

输出 #1

16

输入 #2

2 4

输出 #2

64