F - 高桥的学习教育基础

得分: $600$ 分

问题描述

有一个等差数列，它有 $L$ 个项：$a_0, a_1, a_2, ... , a_{L-1}$。

初始项是 $A$，公差是 $B$。也就是说，有 $a_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$ 得到的余数。

5 3 4 10007

5563

我们的等差数列是 $3, 7, 11, 15, 19$，因此答案是 $37111519$ 除以 $10007$ 的余数，即 $5563$。

4 8 1 1000000

891011

107 10000000000007 1000000000000007 998244353

39122908