今 n 枚の数字が書かれたカードがあります。これらの一部または全部を適当に並べて数字を作ることを考えます。この時作られる数字を全て足した数を求めて下さい。
例えば、 1 と 2 があったら、作られる数字は 1, 2, 12, 21 の 4 つなので、全て足した数は 36 になります。並べた結果同じ数字が出来ても違う並べ方だとしたら別々に足します。たとえば、 1 というカードと 11 というカードがあったら並べて 111 になる並べ方が2通りありますがそれぞれ別のものとして足し合わせます。カードの中にリーディングゼロのカードはありませんし、リーディングゼロになる数字は認めません。答えを1,000,000,007 で割ったものを出力してください。
入力は、以下の形で与えられます。
n
a1
a2
...
an
最初の 1 行にはカードの枚数を表す n(1 ≤ n ≤ 200)、次の n 行にはそれぞれのカードに書かれている数字 ai (0 ≤ ai < 10000) が書かれています。また複数のカードに同じ数字が書かれていることはありません。
作ることの出来る全ての数字の合計を 1,000,000,007 で割ったものを 1 行に出力しなさい。
2 1 2
36
サンプルにあった例です。
2 1 11
234
作られる数字は 1 と 11 と、 111 が 2 通り作られるので全て足して 234 となります。
4 0 4 7 8
135299
04 や 078 といった並べ方は認められないことに注意してください。