等差数列拼接

题目描述

有一个长度为 $L$ 的等差数列 $s_0, s_1, s_2, ..., s_{L-1}$。

这个等差数列的首项是 $A$,公差是 $B$。即 $s_i = A + B \times i$ 成立。

把这个数列的每一项改写为不带前导 0 的十进制表示,然后按顺序连起来读成一个整数。例如,把数列 $3, 7, 11, 15, 19$ 连起来读成的整数是 $37111519$。这个整数除以 $M$ 的余数是多少?

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• 输入均为整数
• $1 \le L, A, B \lt 10^{18}$
• $2 \le M \le 10^9$
• 等差数列的每一项都小于 $10^{18}$