Description

参拜南海观音回来之后，小孙明白了很多。
世界是永世的轮回，每个轮回对应一种缘分的组合，迟早，每个人都会尝遍所有的组合。
好在，不用等到所有的轮回结束，我们就可以用我们有限的智慧预测所有的组合，比如下面这道题。
对于一个无向图，若其中某个点的度数为\(deg\)，那么它的价值是\(base^{deg}\)，一个无向图的价值是它所有点的价值和。
请统计所有\(n\)个点的不同的简单无向图（即没有重边和自环的无向图）的价值和，两个无向图不同当且仅当存在两个点，在一个无向图中有边直接相连，而在另一个无向图中没有。

Format

Input

每个测试点仅包含一组输入数据。
第一行两个正整数\(n,base(1<=n,base<=10^9)\)，含义如题面所述。

Output

输出一行一个正整数，为题目所求答案对\(998244353\)取模的结果。

Sample 1

Input

3 1

Output

24

Limitation

1s, 512MB for each test case.

Source

Vijos Original