Set of Intervals 2
题目描述
给定正整数 n,q。考虑由闭区间组成的集合 S,要求同时满足:
- S 中每个区间均为 [l,r],其中 l,r 是整数且 0≤l≤r≤n。
- 对每个整数 i∈[0,n],单点区间 [i,i] 都属于 S。
- 对任意两个属于 S 的区间 [l0,r0]、[l1,r1],如果l0≤l1<r0≤r1,
则 [l0,l1] 和 [r0,r1] 也必须属于 S。
注意 S 是集合,每个区间至多出现一次。设所有满足条件的集合构成集合族 C,计算
S∈C∑q∣S∣(mod998244353).
这里 ∣S∣ 包括全部 n+1 个必选的单点区间。
输入格式
一行两个整数 n,q。
输出格式
输出一个整数,表示所求结果。
数据范围
1≤n≤105,1≤q<998244353。
样例 1
1 2
12
合法集合分别为 {[0,0],[1,1]} 与 {[0,0],[1,1],[0,1]},贡献为 22+23=12。
样例 2
3 1
22
样例 3
10 3
855061512