#40. sls 的四种膜法

内存限制:128 MiB 时间限制:1000 ms 输入文件:slstxdy.in 输出文件:slstxdy.out
题目类型:传统 评测方式:文本比较
上传者: ce-amtic

题目描述

出于一些众所周知的原因,菜鸡小 B 总被神仙 sls 爆 D。为了挽回颜面,小 B 决定教你 sls 的四种膜法。

给定 k,n,a ,请求出以下四个柿子的值:

\begin{align}T_k(n)&=\sum\limits_{i=0}^n \dbinom{i}{k}a^i\\X_k(n)&=\sum\limits_{i=0}^n \dbinom{k}{i}a^i\\D_k(n)&=\sum\limits_{i=0}^n\dbinom{n}{i}i^k\\Y_k(n)&=\sum\limits_{i=0}^n a^ii^k \end{align}

如果你能求对,小 B 就可以高举slstxdy!的大旗,再也不会被 D 爆啦!由于这个数很大,请对 1004535809 取模。

输入格式

一行三个正整数 k,n,a

输出格式

一行四个整数,依次表示 T_k(n),X_k(n),D_k(n),Y_k(n) 1004535809 取模后的结果。

样例

Sample Input1

2 3 4

Sample Output1

208 25 24 644

Sample Input2

114 514 1919810

Sample Output2

756356622 905338843 601712329 219449979

数据范围与提示

对于 100\% 的数据,保证 1<k\le 2\times 10^5,1<n,a\le 10^9 。本题共有 10 个测试点,每个测试点的数据范围见下表。

测试点编号 k\le n\le a\le
1 2000 2000 10^9
2
3
4 10^9
5
6 10^4
7 3\times 10^4
8 5\times 10^4
9,10 2\times 10^5