#P13008. [AGC035F] Two Histograms

[AGC035F] Two Histograms

题目描述

有一个 NNMM 列的网格。高桥君按照如下方式在每个格子中写入整数。

  • 首先,在所有格子中写入 00
  • 对于 i=1,2,,Ni=1,2,\ldots,N,选择一个整数 ki (0kiM)k_i\ (0\leq k_i\leq M),将第 ii 行从左起前 kik_i 个格子中的整数全部加 11
  • 对于 j=1,2,,Mj=1,2,\ldots,M,选择一个整数 lj (0ljN)l_j\ (0\leq l_j\leq N),将第 jj 列从上起前 ljl_j 个格子中的整数全部加 11

经过上述操作后,每个格子中的数都是 0,1,20,1,2 中的一个。请计算最终可能得到的不同网格的个数,并对 998244353998244353 取模输出。若存在某个格子,其数值不同,则认为两个网格不同。

输入格式

输入从标准输入中给出,格式如下:

NN MM

输出格式

输出最终可能得到的不同网格的个数,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

1 2

输出 #1

8

输入输出样例 #2

输入 #2

2 3

输出 #2

234

输入输出样例 #3

输入 #3

10 7

输出 #3

995651918

输入输出样例 #4

输入 #4

314159 265358

输出 #4

70273732

说明/提示

限制

  • 1N,M5×1051\leq N,M\leq 5\times 10^5
  • N,MN,M 为整数

样例解释 1

如果用 (a,b)(a,b) 表示左边格子的数为 aa,右边格子的数为 bb,则可能得到 (0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)(0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)88 种不同的网格。