题目描述

有一个等差数列，它有$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 时的余数。

输入

一行输入4个整数$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 \leq L,A,B < 10^{18}$

$2 \leq M \leq 10^9$

等差数列的所有项都小于$10^{18}$