← 返回题目列表

AtCoder · abc129_f

F. 高桥的教育和学习基础

中文机器翻译题面 查看原题

分数: 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