#P17681. [Math+Girl×1] Two Steps From Hell / Zero Sum Tree

[Math+Girl×1] Two Steps From Hell / Zero Sum Tree

当前没有测试数据。

P17619

1.5s 512M」

题目描述

为了守护一丝规律,你决定解决如下问题并推广其做法:

对于有标号有根树 TT,设 v(T)v(T) 表示:将 TT 的每个节点 ii 赋权整数 xix_i,满足 −1≤xi≤k-1 \leq x_i \leq k,且任意子树内节点权值和非负,所有节点权值和为 00 的方案数。

对于所有 nn 个点的有标号有根树 TT,求 v(T)v(T) 之和,答案对 998244353998244353 取模。

输入格式

一行两个正整数 n,kn,k。

输出格式

一行一个整数,表示答案。

输入输出样例 #1

输入 #1

4 1

输出 #1

460

输入输出样例 #2

输入 #2

50 5

输出 #2

727571900

输入输出样例 #3

输入 #3

59160 153

输出 #3

911492793

说明/提示

本题开启捆绑测试。

::cute-table{tuack}

子任务 特殊限制 分数
11 n≤10n \leq 10 1010
22 n≤2000n \leq 2000 1515
33 n≤2×105n \leq 2\times10^5 3030
44 k=1k=1 1515
55 - 3030

对于所有数据,1≤n,k≤1071 \leq n,k \leq 10^7。