L - のびたす Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

筑駒 71 期の数学の授業では、「のびたす」という演算が登場しました。 x のびたす y は、x,\ y を文字列として見て連結する操作を表します。

例えば、10 のびたす 20=1020 です。 ある正整数 x に対して、i=1,\ 2,\ldots,\ Q について以下の操作のいずれか片方を選んで行うことを考えます。

  1. x を x+A_i で置き換える
  2. x を x のびたす A_i で置き換える
操作の仕方は 2^Q 通りありますが、それら全てについて最終的な x を求め、その総和を 10^9+7 で割った余りを求めてください。

制約

  • 入力は全て整数である。
  • 1\leq Q\leq10^5
  • 1\leq x\leq10^9
  • 1\leq A_i\leq10^9

入力

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

\(Q\) \(x\)
\(A_1\)
\(A_2\)
\(⋮\)
\(A_Q\)

出力

最終的な x の総和を 10^9+7 で割った余りを出力してください。 出力の最後に改行を忘れないでください。

入力例1

1 3
10

出力例1

323

以下の 2 通りの操作法があります。

  1. 1 回目の操作で x を x+A_1 で置き換える。最終的な x は 3+10=13 となる。
  2. 1 回目の操作で x を x のびたす A_1 で置き換える。最終的な x は 3 のびたす 10=310 となる。
これらの総和は 323 なので、323 を出力します。

入力例2

4 10
12
21
30
9

出力例2

116122282

入力例3

10 102
2109
10329
710923
49832
5437
57432389
78322
572973938
923483
998244353

出力例3

986794595