#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;



const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	assert(b.num != 0);
	return Mod(a) * inv(b);
}
Mod operator/=(Mod &a, const Mod b) {
	assert(b.num != 0);
	return a = a * inv(b);
}

#define MAX_MOD_N 1024

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N],memo[400];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_MOD_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
	
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}


int main() {
	init();
	for (int i = 0; i < 300; ++i) {
		memo[i] = 0;
		for (int j = 0; j <= i; ++j) {
			memo[i] +=comb(i,j)* fact[j];
		}
	}
	int N; cin >> N;
	vector<int>ketas(5);
	vector<int>sums(5);
	bool have_zero = false;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		if (!a) {
			have_zero = true;
		}
		const int keta = to_string(a).size();
		ketas[keta]++;
		sums[keta]+=a;
	}
	Mod ans = 0;
	for (int keta = 1; keta <= 4; ++keta) {
		ketas[keta]--;
		vector<int>under_nums(5);
		
		for (under_nums[1] = 0; under_nums[1] <= ketas[1]; ++under_nums[1]) {
			for (under_nums[2] = 0; under_nums[2] <= ketas[2]; ++under_nums[2]) {
				for (under_nums[3] = 0; under_nums[3] <= ketas[3]; ++under_nums[3]) {
					for (under_nums[4] = 0; under_nums[4] <= ketas[4]; ++under_nums[4]) {
						Mod under_choice = 1;
						int under_size = 0;
						for (int i = 1; i <= 4; ++i) {
							under_size += under_nums[i] * i;
							under_choice *= comb(ketas[i], under_nums[i]);
						}
						int under_count = accumulate(under_nums.begin(), under_nums.end(), 0);
						Mod under_perm =fact[under_count];
						
						int above_sum = accumulate(ketas.begin(), ketas.end(), 0) - accumulate(under_nums.begin(), under_nums.end(), 0);
						Mod above_choice = memo[above_sum];
						ans += Mod(sums[keta]) * under_choice*under_perm*above_choice*mod_pow(Mod(10),under_size);
					}
				}
			}
		}
		ketas[keta]++;
	}
	if (have_zero) {
		ketas[1]--;
		for (int keta = 1; keta <= 4; ++keta) {
			ketas[keta]--;
			vector<int>under_nums(5);

			for (under_nums[1] = 0; under_nums[1] <= ketas[1]; ++under_nums[1]) {
				for (under_nums[2] = 0; under_nums[2] <= ketas[2]; ++under_nums[2]) {
					for (under_nums[3] = 0; under_nums[3] <= ketas[3]; ++under_nums[3]) {
						for (under_nums[4] = 0; under_nums[4] <= ketas[4]; ++under_nums[4]) {
							Mod under_choice = 1;
							int under_size = 0;
							for (int i = 1; i <= 4; ++i) {
								under_size += under_nums[i] * i;
								under_choice *= comb(ketas[i], under_nums[i]);
							}
							int under_count = accumulate(under_nums.begin(), under_nums.end(), 0);
							Mod under_perm = fact[under_count];
							int above_sum = accumulate(ketas.begin(), ketas.end(), 0) - accumulate(under_nums.begin(), under_nums.end(), 0);
							Mod above_choice = memo[above_sum];
							ans -= Mod(sums[keta]) * under_choice*under_perm*above_choice*mod_pow(Mod(10), under_size);
						}
					}
				}
			}
			ketas[keta]++;
		}
	}
	cout << ans << endl;
	return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

Now I have a card with n numbers on it. Consider arranging some or all of these appropriately to make numbers. Find the number obtained by adding all the numbers created at this time.

For example, if you have 1 and 2, you will get 4 numbers 1, 2, 12, 21 so the total number is 36. Even if the same numbers are produced as a result of arranging them, if they are arranged differently, they are added separately. For example, if you have a card called 1 and a card called 11, there are two ways to arrange them so that they are 111, but add them as different ones. There are no leading zero cards among the cards, and we do not accept numbers that lead to zero reading. Output the answer divided by 1,000,000,007.



Input

The input is given in the form:

> n
> a1
> a2
> ...
> an
>

The first line contains n (1 ≤ n ≤ 200), which represents the number of cards, and the next n lines contain the number ai (0 ≤ ai <10000) on each card. Also, the same number is never written on multiple cards.

Output

Output the sum of all the numbers you can make divided by 1,000,000,007 on one line.

Examples

Input

2
1
2


Output

36


Input

2
1
11


Output

234


Input

4
0
4
7
8


Output

135299

### Response

```cpp
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;



const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	assert(b.num != 0);
	return Mod(a) * inv(b);
}
Mod operator/=(Mod &a, const Mod b) {
	assert(b.num != 0);
	return a = a * inv(b);
}

#define MAX_MOD_N 1024

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N],memo[400];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_MOD_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
	
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}


int main() {
	init();
	for (int i = 0; i < 300; ++i) {
		memo[i] = 0;
		for (int j = 0; j <= i; ++j) {
			memo[i] +=comb(i,j)* fact[j];
		}
	}
	int N; cin >> N;
	vector<int>ketas(5);
	vector<int>sums(5);
	bool have_zero = false;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		if (!a) {
			have_zero = true;
		}
		const int keta = to_string(a).size();
		ketas[keta]++;
		sums[keta]+=a;
	}
	Mod ans = 0;
	for (int keta = 1; keta <= 4; ++keta) {
		ketas[keta]--;
		vector<int>under_nums(5);
		
		for (under_nums[1] = 0; under_nums[1] <= ketas[1]; ++under_nums[1]) {
			for (under_nums[2] = 0; under_nums[2] <= ketas[2]; ++under_nums[2]) {
				for (under_nums[3] = 0; under_nums[3] <= ketas[3]; ++under_nums[3]) {
					for (under_nums[4] = 0; under_nums[4] <= ketas[4]; ++under_nums[4]) {
						Mod under_choice = 1;
						int under_size = 0;
						for (int i = 1; i <= 4; ++i) {
							under_size += under_nums[i] * i;
							under_choice *= comb(ketas[i], under_nums[i]);
						}
						int under_count = accumulate(under_nums.begin(), under_nums.end(), 0);
						Mod under_perm =fact[under_count];
						
						int above_sum = accumulate(ketas.begin(), ketas.end(), 0) - accumulate(under_nums.begin(), under_nums.end(), 0);
						Mod above_choice = memo[above_sum];
						ans += Mod(sums[keta]) * under_choice*under_perm*above_choice*mod_pow(Mod(10),under_size);
					}
				}
			}
		}
		ketas[keta]++;
	}
	if (have_zero) {
		ketas[1]--;
		for (int keta = 1; keta <= 4; ++keta) {
			ketas[keta]--;
			vector<int>under_nums(5);

			for (under_nums[1] = 0; under_nums[1] <= ketas[1]; ++under_nums[1]) {
				for (under_nums[2] = 0; under_nums[2] <= ketas[2]; ++under_nums[2]) {
					for (under_nums[3] = 0; under_nums[3] <= ketas[3]; ++under_nums[3]) {
						for (under_nums[4] = 0; under_nums[4] <= ketas[4]; ++under_nums[4]) {
							Mod under_choice = 1;
							int under_size = 0;
							for (int i = 1; i <= 4; ++i) {
								under_size += under_nums[i] * i;
								under_choice *= comb(ketas[i], under_nums[i]);
							}
							int under_count = accumulate(under_nums.begin(), under_nums.end(), 0);
							Mod under_perm = fact[under_count];
							int above_sum = accumulate(ketas.begin(), ketas.end(), 0) - accumulate(under_nums.begin(), under_nums.end(), 0);
							Mod above_choice = memo[above_sum];
							ans -= Mod(sums[keta]) * under_choice*under_perm*above_choice*mod_pow(Mod(10), under_size);
						}
					}
				}
			}
			ketas[keta]++;
		}
	}
	cout << ans << endl;
	return 0;
}
```