#P7003. [2017年成都七中集训]第一题

    ID: 6834 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF2100提高线性递推组合数乘法递推逆元线性递推模逆元快速幂等比数列求和

[2017年成都七中集训]第一题

题目描述

给定 n,b,kn,b,k,求

∑i=1n(ik)bi\sum_{i=1}^n\binom{i}{k}b^i

对 998244353998244353 取模的结果。

输入格式

一行三个整数 n,b,kn,b,k。

输出格式

输出一个整数,表示所求结果对 998244353998244353 取模后的值。

样例

2 2 2
4

数据范围

  • 对于 20%20\% 的数据,n≤100000n\le 100000。
  • 对于另外 30%30\% 的数据,b=2b=2。
  • 对于 70%70\% 的数据,k≤2000k\le 2000。
  • 对于所有数据,1≤k≤5000001\le k\le 500000,1≤n≤10181\le n\le 10^{18},2≤b<9982443532\le b<998244353。

原 PDF 题面