配点: $600$ 点

問題文

長さ $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$ で割ったあまりはいくらでしょうか。

制約

• 入力はすべて整数である
• $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