#H1038. 垃圾问题

垃圾问题

题目描述

まりな是一只优秀的人工智能,她发现最近处理的问题有一些十分相似的问题。由于这类问题太多了,まりな为了设计与维斯考特的作战方案,她决定把这类问题交给你来处理。

这类问题形同:对于一个给定的 n,kn,k 和数列 pp,问下面这个式子的值:

i1=1ni2=1i1i3=1i2...ik=1ik1pik\sum_{i_1=1}^n\sum_{i_2=1}^{i_1}\sum_{i_3=1}^{i_2}...\sum_{i_k=1}^{i_{k-1}}p_{i_k}

由于まりな认为这种重复的计算问题毫无意义,于是为了减轻你的负担,她只要求你给她对 1e9 ⁣+ ⁣71e9\!+\!7 取模后的答案。

输入格式

输入共两行:
第一行两个整数 n,kn,k
第二行四个整数 a,b,c,da,b,c,d
aa 表示数列 pp 的第一项,且 pi=(pi1×b+c) mod d(i>1)p_i=(p_{i-1}\times b+c)\ mod\ d(i>1)

输出格式

共一行一个数表示答案。

5 2
8 6 9 15
115
8 3
1 2 3 10

432

数据范围与提示

对于 20%20\% 的数据 n10n\leq 10k5k\leq 5
对于 50%50\% 的数据 n2×105n\leq 2\times10^5k50k\leq 50
对于 100%100\% 的数据 0<n,k1070< n,k\leq 10^71<a,b,c,d1091< a,b,c,d\leq 10^9