Type: Default 1000ms 256MiB

画图游戏

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知, 过年团聚后玩游戏是必不可少的, 大明想到了一个好玩的游戏

题目描述

给你一个 n×mn \times m 的矩阵, 要求你用 mm1×n1 \times n 的木棍将矩阵中所有的方格覆盖, 一共有多少不同的摆放方案?

注意: 答案可能很大, 需要对 998244353 取模

输入格式

两个整数 n,mn, m

输出格式

输出一个整数, 表示有多少摆放方案.

样例 #1

样例输入 #1

3 10

样例输出 #1

28

数据范围

0n,m1060 \le n, m \le 10^{6}