#P17984. Set of Intervals 2

Set of Intervals 2

Set of Intervals 2

题目描述

给定正整数 n,qn,q。考虑由闭区间组成的集合 SS,要求同时满足:

  1. SS 中每个区间均为 [l,r][l,r],其中 l,rl,r 是整数且 0≤l≤r≤n0\le l\le r\le n。
  2. 对每个整数 i∈[0,n]i\in[0,n],单点区间 [i,i][i,i] 都属于 SS。
  3. 对任意两个属于 SS 的区间 [l0,r0][l_0,r_0]、[l1,r1][l_1,r_1],如果l0≤l1<r0≤r1,l_0\le l_1<r_0\le r_1, 则 [l0,l1][l_0,l_1] 和 [r0,r1][r_0,r_1] 也必须属于 SS。

注意 SS 是集合,每个区间至多出现一次。设所有满足条件的集合构成集合族 C\mathcal C,计算

∑S∈Cq∣S∣(mod998244353).\sum_{S\in\mathcal C}q^{|S|}\pmod{998244353}.

这里 ∣S∣|S| 包括全部 n+1n+1 个必选的单点区间。

输入格式

一行两个整数 n,qn,q。

输出格式

输出一个整数,表示所求结果。

数据范围

1≤n≤1051\le n\le10^5,1≤q<9982443531\le q<998244353。

样例 1

1 2
12

合法集合分别为 {[0,0],[1,1]}\{[0,0],[1,1]\} 与 {[0,0],[1,1],[0,1]}\{[0,0],[1,1],[0,1]\},贡献为 22+23=122^2+2^3=12。

样例 2

3 1
22

样例 3

10 3
855061512