#P5437. 【XR-2】约定

【XR-2】约定

题目背景

「小圆,不要走!这一分离,我们何时才能重逢?」

「小焰,我们一定还会相见的!在那之前,我们只是短暂的离别啊......」

题目描述

只因为那一句约定,小焰开始了看不到尽头的等待。

约定在小焰心中幻化成了一张 nn 个点的图。一开始,这是一张完全图,其中点的编号从 11nn,连接点 i,ji,j 的边的权值为 (i+j)k(i+j)^k

然而等待的过程中,岁月也在逐渐消磨着她的信仰,因此图中的一些边被随机地删掉了。最终,图变成了一棵 nn 个点的树,永远地留在了小焰的心中。

很久很久以后,小焰的魔力耗尽,在痛苦与绝望之中濒临崩溃。而就在这时,小圆终于来找小焰了。为了拯救自己唯一的朋友,她必须知道这棵树边权和的期望值对 998244353998244353 取模的结果是多少。

你能帮小圆求出答案,让她完成那个约定吗?

输入格式

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

输出格式

一行一个整数,表示答案对 998244353998244353 取模后的值。

3 1

8

4 3

450

1926 817

984167516

提示

【样例 11 说明】

这个完全图有 33 个节点,33 条边,形成了一个环。
这些边的权分别为:3,4,53,4,5
最后形成的树也有 33 种可能,权值分别为:7,8,97,8,9
期望值为 88

【数据规模与约定】

本题采用捆绑测试。

Subtask 1(5 points):1n51 \le n \le 51k101\le k \le 10
Subtask 2(11 points):k=1k = 1
Subtask 3(11 points):1n,k200001 \le n,k \le 20000
Subtask 4(13 points):1n,k1051 \le n,k \le 10^5
Subtask 5(23 points):1k1051 \le k \le 10^5
Subtask 6(37 points):无特殊限制。

对于 100%100\% 的数据,1n998244352,1k1071\le n \le 998244352,1\le k \le 10^7


「抱歉,让你久等了...... 你一直努力到了今天吧......」

「小圆......」

「来,我们走吧。今后我们永不分离......」

「是啊,我等这一刻——望眼欲穿。」