Cho một mảng ~a~ gồm ~n~ số nguyên dương ~(0 < a_{i} < 10^9)~.

Định nghĩa giá trị của một mảng là số nguyên thu được bằng cách viết liền các phần tử của mảng đó theo thứ tự từ trái sang phải.

Ví dụ, nếu mảng là ~[12, 3, 45]~, giá trị của mảng sẽ là ~12345~.

Yêu cầu: Hãy tính tổng giá trị của tất cả các hoán vị của mảng ~a~. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \le 200)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_{n}~ ~(a_{i} < 10^9)~.

Output

In ra một số nguyên duy nhất là tổng giá trị của mọi hoán vị lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

2
12 3

Sample Output 1

435

Notes

Trong ví dụ trên, có ~2~ hoán vị:

• ~[12, 3] \rightarrow 123~

• ~[3, 12] \rightarrow 312~