C-Papy 的数列求和_牛客挑战赛87

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Papy 是出题组唯一的高中生，CirnoNine 为了欺负 Papy，给了他一道高中数学经典的等差乘等比的数列求和式：

$\displaystyle f(n,a,b,q) = \sum\limits_{i=1}^{n} \Big( (a\times i+b)\times q^i \Big)$

$\hspace{15pt}$ 由于这个答案可能很大，CirnoNine 只要求 Papy 回答 $f(n,a,b,q) \bmod m$ 即可。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入四个整数 ，含义如题。
第二行输入一个二进制整数 ，保证  不存在前导 ，含义如题。

除此之外，保证单个测试文件的二进制整数的长度之和（即  之和）不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数表示 。

示例1

输入

复制

3
998244353 0 1 2
1
998244353 1 2 3
101
114514 191 9 810
1010

输出

复制

2
2367
74508

说明

对于第一组测试数据，，带入可得 。

对于第二组测试数据，，带入可得 。

对于第三组测试数据，，带入可得 。

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。