6040 -- 【九校1D2T1】锻造

Description

“欢迎啊，老朋友。”

一阵寒暄过后，厂长带他们参观了厂子四周，并给他们讲锻造的流程。

“我们这里的武器分成若干的等级，等级越高武器就越厉害，并且对每一等级的武器都有两种属性值 b 和 c，但是我们初始只能花 a 个金币来生产 1 把 0 级剑……”

“所以你们厂子怎么这么垃圾啊，不能一下子就造出来 999 级的武器吗？”勇者不耐烦的打断了厂长的话。

“别着急，还没开始讲锻造呢……那我们举例你手中有一把 x 级武器和一把 y 级武器 (y = max(x−1,0))，我们令锻造附加值 k = min(cx ,by )，则你有k/cz的概率将两把武器融合成一把 x + 1 级的武器。”

“……但是，锻造不是一帆风顺的，你同样有 1 −k/cx的概率将两把武器融合成一把 max(x − 1,0) 级的武器……”

勇者听完后暗暗思忖，他知道厂长一定又想借此机会坑骗他的零花钱，于是求助这个村最聪明的智者——你，来告诉他，想要强化出一把 n 级的武器，其期望花费为多少？

由于勇者不精通高精度小数，所以你只需要将答案对 998244353(7 ×17 × 2^23 + 1，一个质数 ) 取模即可。

Input

第一行两个整数 n,a，含义如题所示。

为了避免输入量过大，第二行五个整数 bx,by,cx,cy,p，按照下列代码来生成 b 和 c 数组。

b[0]=by+1;c[0]=cy+1;

for(int i=1;i<n;i++){

b[i]=((long long)b[i-1]*bx+by)%p+1;

c[i]=((long long)c[i-1]*cx+cy)%p+1;

}

Output

输出一行一个整数，表示期望花费。

Sample Input

1.4.1 样例 1 输入

0 6432

4602677 3944535 2618884 6368297 9477531

1.4.2 样例 1 输出

6432

1.4.3 样例 2 输入

1 3639650

6136976 5520115 2835750 9072363 9302097

1.4.4 样例 2 输出

150643649

1.4.5 样例 3 输入

10 2

2 33 6 66 2333333

1.4.6 样例 3 输出

976750710

1.4.7 样例 4 输入

200 5708788

0 0 0 0 1

1.4.8 样例 4 输出

696441597

Sample Output

 

Hint

 

 

 

 

 

 

 

然后我的AC代码MLE了>_<

code：

1 #include
        
          2 #include
         
           3 #define N 10000005 4 using namespace std; 5 const int mod=998244353; 6 int b[N],c[N]; 7 int E[N]; 8 int bx,by,cx,cy,p; 9 int inv[N];10 int main() {11 //    freopen("forging.in","r",stdin);12 //    freopen("forging.out","w",stdout);13     int n,a;14     cin>>n>>a;15     cin>>bx>>by>>cx>>cy>>p;16     b[0]=by+1;17     c[0]=cy+1;18     for(int i=1; i
         
        

over