[R56E]移位和 - 代码源竞赛平台

时空限制

1S/256M

题目描述

给定位数为 $n$ 的十进制整数 $x$，将 $x$ 视为一个长度为 $n$ 的数字串 $a_1 a_2 \dots a_n$（其中 $a_1 \neq 0$），定义一次循环右移一位操作将数字串变为 $a_n a_1 \dots a_{n-1}$。

对于任意非负整数 $i$，令 $f(i)$ 表示对 $x$ 连续进行 $i$ 次循环右移一位后得到的整数（结果允许出现前导零，且每次求 $f$ 的值时并不会真的改变 $x$ 的值）。

给定一个长度为 $m$ 的序列 $l_1,\dots,l_m$，你需要求出 $\sum_{i=1}^m f(l_i)$ 的值模 $10^9+7$ 后的结果。

格式

输入格式

第一行包含两个正整数 $n,m$，分别表示整数的位数和 $l$ 序列的长度。

第二行包含一个位数为 $n$ 的整数，表示 $x$。

第三行包含 $m$ 个整数，表示序列 $l$。

输出格式

输出一行一个整数表示 $\sum_{i=1}^m f(l_i)$ 的值模 $10^9+7$ 后的结果。

样例

样例输入 #1

2 5
56
0 1 1 3 4

样例输出 #1

307

样例输入 #2

6 6
394456
2 3 1 4 0 8

样例输出 #2

3063822

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$m\le$
$1$	$10$	$2000$	$2000$
$2$	$20$		$10^6$
$3$	$70$	$10^6$

对于 $100\%$ 的数据，满足 $1\le n,m\le10^6,0\le l_i\le10^9$。