#ABC129F. Takahashi's Basics in Education and Learning

Takahashi's Basics in Education and Learning

题目描述

There is an arithmetic progression with LL terms: s0,s1,s2,...,sL1s_0, s_1, s_2, ... , s_{L-1}.

The initial term is AA, and the common difference is BB. That is, si=A+B×is_i = A + B \times i holds.

Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3,7,11,15,193, 7, 11, 15, 19 would be concatenated into 3711151937111519. What is the remainder when that integer is divided by MM?

有一个算术级数有 LL 项: s0,s1,s2,...,sL1s_0, s_1, s_2, ... , s_{L-1} .

首项为 AA ,公差为 BB 。也就是说, si=A+B×is_i = A + B \times i 成立。

考虑将以十进制写成的项连接起来得到的不带前导零的整数。例如,将序列 3,7,11,15,193, 7, 11, 15, 19 连接成 3711151937111519 。这个整数除以 MM 的余数是多少?

输入格式

输入内容按以下格式标准输入:

LL AA BB MM

输出格式

打印连接项得到的整数除以 MM 后的余数。

样例 #1

样例输入 #1

5 3 4 10007

样例输出 #1

5563

样例 #2

样例输入 #2

4 8 1 1000000

样例输出 #2

891011

样例 #3

样例输入 #3

107 10000000000007 1000000000000007 998244353

样例输出 #3

39122908

说明

数据规模与约定

  • 所有输入值均为整数。
  • 1L,A,B<10181 \leq L, A, B \lt 10^{18}
  • 2M1092 \leq M \leq 10^9
  • 算术级数中的所有项都小于 101810^{18}

样例 11 解释

我们的算术级数是 3,7,11,15,193, 7, 11, 15, 19 ,所以答案是 3711151937111519 mod 1000710007 ,即 55635563