该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc129_f [ABC129F] Takahashi's Basics in Education and Learning

题目描述

给定一个长度为 $L$ 的等差数列 $s_0, s_1, s_2, \ldots, s_{L-1}$。

这个等差数列的首项为 $A$，公差为 $B$。也就是说，$s_i = A + B \times i$。

请将这个数列的每一项转化为没有前导零的十进制表示，然后依次连接起来，得到一个新的整数。例如，数列 $3, 7, 11, 15, 19$ 连接后得到的整数是 $37111519$。请计算这个整数除以 $M$ 的余数。

输入格式

输入从标准输入中给出，格式如下：

$L$ $A$ $B$ $M$

输出格式

输出将数列各项连接后得到的整数除以 $M$ 的余数。

样例 1

输入

5 3 4 10007

输出

5563

样例 2

输入

4 8 1 1000000

输出

891011

样例 3

输入

107 10000000000007 1000000000000007 998244353

输出

39122908

说明/提示

限制条件

• 输入均为整数。
• $1 \leq L, A, B < 10^{18}$
• $2 \leq M \leq 10^9$
• 等差数列的所有元素均小于 $10^{18}$。

样例解释 1

考虑的等差数列为 $3, 7, 11, 15, 19$，连接后得到 $37111519$，用 $10007$ 取余得到 $5563$，所以答案为 $5563$。

由 ChatGPT 4.1 翻译