Card

Time limit4sMemory limit512 MB

Summary

Given n distinct cards, sum all numbers formed by arranging any nonempty subset in any order, counting duplicate values separately, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

There are n cards, each with a number written on it. Consider arranging some or all of them in any order to form a number. Find the sum of all numbers that can be formed this way.

For example, with 1 and 2, the numbers that can be formed are 1, 2, 12, and 21, so the sum of all of them is 36. If the same number results from an arrangement, but the arrangements differ, each is added separately. For example, with a card 1 and a card 11, there are 2 ways to arrange them to get 111, and each is counted as a distinct number in the sum. No card has a leading zero, and numbers with a leading zero are not allowed. Output the answer modulo 1,000,000,007.

Input

The input is given in the following format.

n
a1
a2
...
an

The first line contains the number of cards n (1 ≤ n ≤ 200), and the next n lines each contain the number ai written on a card (0 ≤ ai < 10000). No two cards have the same number written on them.

Output

Print the sum of all numbers that can be formed, modulo 1,000,000,007, on a single line.

Examples3

Example 1
Input
```
2
1
2
```
Expected output
```
36
```
Example 2
Input
```
2
1
11
```
Expected output
```
234
```
Example 3
Input
```
4
0
4
7
8
```
Expected output
```
135299
```