#P10711. 老生常谈

    ID: 9829 传统题 6000ms 512MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-下降阶乘基底运算二项式反演曲棍球棒恒等式交换求和顺序导数积分转化组合数乘法递推阶乘逆元预处理批量求逆线性筛快速幂增量维护

老生常谈

题目描述

给定正整数 n,m,xn,m,x,定义

$$f_0(x)=x^n,\qquad f_j(x)=\sum_{i=0}^{x} f_{j-1}(i)\quad(j\ge1).$$

求 fm(x)f_m(x) 对 998244353998244353 取模的结果。

输入格式

一行三个整数 n,m,xn,m,x。

输出格式

输出一行一个整数,表示 fm(x) mod 998244353f_m(x)\bmod 998244353。

样例 1

1 1 4
10

样例 2

5 1 4
1300

样例 3

1 9 19
13123110

样例 4

114 514 1919810
693970832

数据范围

1≤n≤1071\le n\le10^7,1≤m,x≤4×1081\le m,x\le4\times10^8。

测试点 nn 上界 mm 上界 xx 上界
1 100
2–3 10710^7 10710^7 10310^3
4–5 10510^5
6 10610^6
7 10710^7
8 1 4×1084\times10^8
9 3
10 10510^5
11–12 4×1084\times10^8
13 10610^6 10710^7
14–15 4×1084\times10^8
16 10710^7 1
17 3
18 10510^5
19 10710^7 10710^7
20 4×1084\times10^8

原 PDF 题面