#P5442. 【XR-2】约定 (加强版)

【XR-2】约定 (加强版)

题目背景

原题链接:P5437

其实在比赛时就想放上这个加强版了qwq
但是团队成员都强烈反对,于是就在赛后放上来啦

题目描述

有一个 nn 个点的完全图,编号从 11nn
连接 iijj 节点的边,权值为 (i+j)k(i+j)^k
定义一棵树的权值为其所有边的权值和。
从这个图的所有生成树中随机选择一个,求其权值的期望。
需要将答案对 998244353998244353 取模。

输入格式

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

输出格式

一行一个整数表示答案对 998244353998244353 取模的结果。

输入数据 1

3 1

输出数据 1

8

输入数据 2

4 3

输出数据 2

450

输入数据 3

1926 817

输出数据 3

984167516

输入数据 4

998244353 1

输出数据 4

998244352

提示

数据范围:

1n10100001\le n \le 10^{10000}
1k1071\le k \le 10^7