You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

辰辰和小北在潍坊北辰大学附近游玩，看到一大群学生在排队，不知在干什么。他们急忙跑过去。

题目描述

实行书院制管理是潍坊北辰大学教改实验中一个至关重要的环节。潍坊北辰大学致力于培养拔尖创新型人才，实行“$2+2$”培养模式，大三才分专业，书院可增强学生的归属感和集体观念，营造师生交流互动的良好环境。不同年级、不同专业的老师和学生在书院里互相交流、互相学习，老师给学生学业、生活上以指导和帮助，学生的新思想可以给老师启发，教学相长、互相促进。

由于潍坊北辰大学有多个书院，每个同学有自己想进入的书院，每个书院也有自己想招收的学生，于是就有了书院双选制。

芷橙书院是潍坊北辰大学最受欢迎的书院之一，每级招生都会有大量的新生报名，远远超出了芷橙书院的招生量。于是大学长北北和辅导老师不得不在新生中选择进入书院的最终人选。

2222 级共有 $n$ 个人报名了芷橙书院，大学长北北按照预期招生数量在其中选择了 $m$ 个人（$m\le n$），通知了他们将会被芷橙书院录取，并通知了剩下的 $n-m$ 个人很遗憾不能被录取。但是天有不测风云，由于宿舍床位紧张，芷橙书院实际只能招收 $k$ 名新生（$k\le m$），于是辅导老师在大学长北北选出的 $m$ 个人中又挑选了 $k$ 个人最终录取，并给剩下的 $m-k$ 个人发了安慰奖。这样，最终结果是芷橙书院总共录取了 $k$ 个人，有 $m-k$ 个人获得了安慰奖，最后剩下的 $n-m$ 个人得知了自己没有被录取。但是这 $k$ 个人中，突然又有 $l$ 个人因种种原因无法来此书院。

考虑每个同学最终得到的结果为局面：两个局面不同，当且仅当存在至少一名同学得到了不同的结果（被录取或安慰奖或未录取或来不了）。现在 $m$ 和 $k$ 和 $l$ 都是未知的（任意取值的），求一共有多少种可能的局面。（即，已知 $n$ ，枚举所有合法的 $m$ 和 $k$ 和 $l$，分别求出局面数之后，再总求和就是所求）答案对 $2^{64}$ 取模。

输入输出

输入

由于 $n,tmp$ 过大，所以无需读入 $n,tmp$，读入 $m,k,p,q$，$n$ 的数位长度为 $m$，$tmp$ 的数位长度为 $k$， $n,tmp$ 的生成如下。

输出

一行，一个数，表示答案，即局面数，答案要加上 $tmp$，无需再取模。

Samples

2 3 1 1

16777339

数据范围

对于所有数据，$m\le 5\times 10^7,k\le 5\times 10^3$

注意，当 $n\le 10^{18}$ 时，$tmp\le 10^{18}$。

不要问需不需要高精度，真的不需要，需要也只用一点点 $qwq$！

您可以直接 $copy$ 以下代码，已经自带读入和生成，您只需要在 $Solve$ 函数内完成代码即可。

#include<bits/stdc++.h>
using namespace std;
int n[50000005], tmp[50000005], m, k, p, q;
void Solve () {
	
	//在这里写您的代码 
	
	
	return; 
}
int main() {
	scanf("%d%d%d%d", &m, &k, &p, &q);
	for (int i = 1; i <= m; ++ i) n[i] = (n[i - 1] * p + q) % 10;
	for (int i = 1; i <= k; ++ i) tmp[i] = (tmp[i - 1] * q + p) % 10;
	Solve();
	return 0;
}

其中 $n[i]$ 表示原题中 $n$ 从左开始数的第 $i$ 位，$tmp$ 数组同理。