题目描述

この等差数列の初項は $A$、公差は $B$ です。つまり、$s_i\ =\ A\ +\ B\ \times\ i$ が成り立ちます。

この数列の各項を、先頭に $0$ の無い十進法表記に直し、順につなげて読んでできる整数を考えます。たとえば、数列 $3,\ 7,\ 11,\ 15,\ 19$ をつなげて読んでできる整数は $37111519$ となります。この整数を $M$ で割ったあまりはいくらでしょうか。

输入格式

入力は以下の形式で標準入力から与えられます。

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

输出格式

数列の各項をつなげて読んだ整数を $M$ で割ったあまりを出力してください。

题目大意

有一等差数列，首项为 $A$，公差为 $B$，长度为 $L$。

现在把这个数列中所有数拼起来（e.g. $3,7,11,15,19->37111519$）。

问拼起来的这个数 $\bmod M$ 的值。

$1\le L,A,B \le 10^{18},1\le M\le 10^9$

5 3 4 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}$ 未満

Sample Explanation 1

考える等差数列は $3,\ 7,\ 11,\ 15,\ 19$ なので，$37111519$ を $10007$ で割ったあまりである $5563$ が答えです．