分数: 600 点
问题陈述
给你 <var>Q</var> 个整数元组 <var>(L_i, A_i, B_i, M_i)</var>。对于每个元组,回答以下问题。有一个算术级数 L 条款: s_0, s_1, s_2, ... , s_{L-1}.
初始期限是 A,共同的区别是 B。也就是说, s_i = A + B \times i 成立。
考虑通过连接以十为基数且不带前导零的项所获得的整数。例如,序列 3, 7, 11, 15, 19 将被连接成 37111519。该整数除以余数是多少 M?
约束
- 输入中的所有值都是整数。
- 1 \leq L, A, B < 10^{18}
- 2 \leq M \leq 10^9
- 等差数列中的所有项均小于 10^{18}.
输入
输入由标准输入按以下格式给出:
L A B M
输出
打印通过连接各项获得的整数除以时的余数 M.
示例输入 1
5 3 4 10007
示例输出 1
5563
我们的算术级数是 3, 7, 11, 15, 19,所以答案是 37111519 模组 10007,即 5563.
示例输入 2
4 8 1 1000000
示例输出 2
891011
示例输入 3
107 10000000000007 1000000000000007 998244353
示例输出 3
39122908