题目描述

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

这类问题形同：对于一个给定的 $n,k$ 和数列 $p$，问下面这个式子的值：

$$\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\!+\!7$ 取模后的答案。

输入格式

输入共两行：
第一行两个整数 $n,k$。
第二行四个整数 $a,b,c,d$。
$a$ 表示数列 $p$ 的第一项，且 $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\%$ 的数据 $n\leq 10$，$k\leq 5$。
对于 $50\%$ 的数据 $n\leq 2\times10^5$，$k\leq 50$。
对于 $100\%$ 的数据 $0< n,k\leq 10^7$，$1< a,b,c,d\leq 10^9$。