#P3453. tyvj 1858 XLkxc

    ID: 2653 传统题 1000ms 512MiB 尝试: 507 已通过: 135 难度: 7 上传者: 标签>CF2200提高+/省选-连续点值插值阶乘逆元预处理前后缀分解快速幂

tyvj 1858 XLkxc

题目背景

神犇 LYD 虐完 HEOI 之后给傻 X XLk 出了一题:

SHY 是某国的公主,平时的一大爱好是读诗 …\dots (中间略) …\dots 结果  mod p\bmod p 就可以了

题目描述

给定 k,a,n,d,pk,a,n,d,p

f(i)=1k+2k+3k+⋯+ikf(i)=1^k+2^k+3^k+\dots +i^k

g(x)=f(1)+f(2)+f(3)+⋯+f(x)g(x)=f(1)+f(2)+f(3)+\dots +f(x)

求 (g(a)+g(a+d)+g(a+2d)+......+g(a+nd)) mod p(g(a)+g(a+d)+g(a+2d)+......+g(a+nd)) \bmod p

输入格式

有多组数据。

第一行输入数据组数 TT;

以下 TT 行,每行四个整数,代表这组数据中的 k,a,n,dk,a,n,d。

输出格式

共 TT 行,每行一个整数,表示计算出的结果。

5
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
5
5
5
5
5

数据范围

对于 100%100\% 的数据:$1\leq k\leq 123,0\leq a,n,d\leq 123456789,p=1234567891$