题目描述

有一个等差数列，包含$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