#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;
bool zero_FLG;
ll POW[1000];
ll num_count[5]; //1～4桁の数がいくつあるか
ll digit_sum[5]; //1～4桁の数の合計
ll nCm[200][200]; //抽出する場合の数
ll mult_num[200]; //n!の表
ll mult_sum[200]; //ΣnPk(k = 0～n)の表
ll dp[5][200][801]; //dp[桁数][右側の数字の使用個数][位置(右側の数字の合計桁数)] = 場合の数

int get_digit(ll num){
	if(num == 0)return 1;

	int count = 0;

	while(num > 0){
		count++;
		num /= 10;
	}
	return count;
}

void make_dp(){

	for(int digit = 1; digit <= 4; digit++){
		for(int use_num = 0; use_num < 200; use_num++){
			for(int loc = 0; loc < 801; loc++)dp[digit][use_num][loc] = 0;
		}
	}

	ll sum_digit,sum_use,tmp;
	int work[5];

	//★★1～4桁の数が、ある場所に来る場合の数を求める[ある場所の右に来る数列を計算する]★★
	for(int digit = 1; digit <= 4; digit++){ //計算したい桁の数

		for(int num1 = 0; num1 <= num_count[1]; num1++){ //1桁の数の使用数
			if(digit == 1 && num1 == 0)continue; //1桁の数を計算したいなら、少なくとも1つ必要(自分の分)

			for(int num2 = 0; num2 <= num_count[2]; num2++){
				if(digit == 2 && num2 == 0)continue;

				for(int num3 = 0; num3 <= num_count[3]; num3++){
					if(digit == 3 && num3 == 0)continue;

					for(int num4 = 0; num4 <= num_count[4]; num4++){
						if(digit == 4 && num4 == 0)continue;

						work[1] = num1;
						work[2] = num2;
						work[3] = num3;
						work[4] = num4;

						work[digit] -= 1; //自分を除く

						sum_use = 0;
						sum_digit = 0;

						for(int i = 1; i <= 4; i++){
							sum_use += work[i];
							sum_digit += i*work[i];
						}

						//★★数字を抽出する場合の数を掛ける★★
						tmp = 1;
						for(int i = 1; i <= 4; i++){
							if(digit != i){
								tmp *= nCm[num_count[i]][work[i]];
							}else{ //digit == i
								tmp *= nCm[num_count[i]-1][work[i]];
							}
							tmp %= MOD;
						}
						tmp *= mult_num[sum_use]; //sum_use個の数字の並べ方はsum_use!通り
						tmp %= MOD;

						dp[digit][sum_use][sum_digit] += tmp;
						dp[digit][sum_use][sum_digit] %= MOD;
					}
				}
			}
		}
	}
}

ll calc(){

	make_dp();

	ll ret = 0;
	ll tmp;
	for(int digit = 1; digit <= 4; digit++){
		for(int use_num = 0; use_num < 200; use_num++){
			for(int loc = 0; loc < 801; loc++){

				tmp = dp[digit][use_num][loc]*POW[loc];
				tmp %= MOD;
				tmp *= mult_sum[N-(use_num+1)]; //★左側に並べる数字の場合の数の総和★
				tmp %= MOD;
				tmp *= digit_sum[digit];
				tmp %= MOD;
				ret += tmp;
				ret %= MOD;
			}
		}
	}
	return ret;
}

int main(){

	//10の累乗を計算する
	POW[0] = 1;
	for(int i = 1; i < 801; i++){
		POW[i] = POW[i-1]*10;
		POW[i] %= MOD;
	}

	//ΣnPkおよびn!を求める
	ll number,tmp_sum;
	for(ll a = 199;a >= 0; a--){
		tmp_sum = a+1; //aP0 == 1,aP1 = a
		number = a;
		for(ll k = 1; k <= a-1; k++){
			number *= (a-k);
			number %= MOD;
			tmp_sum += number;
			tmp_sum %= MOD;
		}
		mult_num[a] = number; //a!
		mult_sum[a] = tmp_sum; //ΣaPk
	}

	//コンビネーションを求める
	nCm[0][0] = 1;
	for(int n = 1; n < 200; n++) {
		for (int k = 0; k <= n; k++) {
			if(k > 0){
				nCm[n][k] = nCm[n-1][k]+nCm[n-1][k-1];
			}else{ //k == 0
				nCm[n][k] = 1;
			}
			nCm[n][k] %= MOD;
		}
	}

	mult_num[0] = 1; //0! = 1

	zero_FLG = false; //0が登場したかどうかのフラグ
	for(int i = 1; i <= 4; i++){
		num_count[i] = 0;
		digit_sum[i] = 0;
	}

	scanf("%d",&N);

	int tmp_digit;
	ll tmp;

	for(int i = 0; i < N; i++){
		scanf("%lld",&tmp);
		if(tmp == 0){
			zero_FLG = true;
		}
		tmp_digit = get_digit(tmp);
		num_count[tmp_digit]++; //tmp_digit桁の数の個数を計上
		digit_sum[tmp_digit] += tmp; //tmp_digit桁の数の総和を求める
	}

	ll ans = calc();
	if(zero_FLG){
		N--; //0は入力されても最大1つ(問題仕様)
		num_count[1]--;
		ans -= calc();
		if(ans < 0)ans += MOD;
	}

	printf("%lld\n",ans);

	return 0;
}


### Prompt

Develop a solution in cpp 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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;
bool zero_FLG;
ll POW[1000];
ll num_count[5]; //1～4桁の数がいくつあるか
ll digit_sum[5]; //1～4桁の数の合計
ll nCm[200][200]; //抽出する場合の数
ll mult_num[200]; //n!の表
ll mult_sum[200]; //ΣnPk(k = 0～n)の表
ll dp[5][200][801]; //dp[桁数][右側の数字の使用個数][位置(右側の数字の合計桁数)] = 場合の数

int get_digit(ll num){
	if(num == 0)return 1;

	int count = 0;

	while(num > 0){
		count++;
		num /= 10;
	}
	return count;
}

void make_dp(){

	for(int digit = 1; digit <= 4; digit++){
		for(int use_num = 0; use_num < 200; use_num++){
			for(int loc = 0; loc < 801; loc++)dp[digit][use_num][loc] = 0;
		}
	}

	ll sum_digit,sum_use,tmp;
	int work[5];

	//★★1～4桁の数が、ある場所に来る場合の数を求める[ある場所の右に来る数列を計算する]★★
	for(int digit = 1; digit <= 4; digit++){ //計算したい桁の数

		for(int num1 = 0; num1 <= num_count[1]; num1++){ //1桁の数の使用数
			if(digit == 1 && num1 == 0)continue; //1桁の数を計算したいなら、少なくとも1つ必要(自分の分)

			for(int num2 = 0; num2 <= num_count[2]; num2++){
				if(digit == 2 && num2 == 0)continue;

				for(int num3 = 0; num3 <= num_count[3]; num3++){
					if(digit == 3 && num3 == 0)continue;

					for(int num4 = 0; num4 <= num_count[4]; num4++){
						if(digit == 4 && num4 == 0)continue;

						work[1] = num1;
						work[2] = num2;
						work[3] = num3;
						work[4] = num4;

						work[digit] -= 1; //自分を除く

						sum_use = 0;
						sum_digit = 0;

						for(int i = 1; i <= 4; i++){
							sum_use += work[i];
							sum_digit += i*work[i];
						}

						//★★数字を抽出する場合の数を掛ける★★
						tmp = 1;
						for(int i = 1; i <= 4; i++){
							if(digit != i){
								tmp *= nCm[num_count[i]][work[i]];
							}else{ //digit == i
								tmp *= nCm[num_count[i]-1][work[i]];
							}
							tmp %= MOD;
						}
						tmp *= mult_num[sum_use]; //sum_use個の数字の並べ方はsum_use!通り
						tmp %= MOD;

						dp[digit][sum_use][sum_digit] += tmp;
						dp[digit][sum_use][sum_digit] %= MOD;
					}
				}
			}
		}
	}
}

ll calc(){

	make_dp();

	ll ret = 0;
	ll tmp;
	for(int digit = 1; digit <= 4; digit++){
		for(int use_num = 0; use_num < 200; use_num++){
			for(int loc = 0; loc < 801; loc++){

				tmp = dp[digit][use_num][loc]*POW[loc];
				tmp %= MOD;
				tmp *= mult_sum[N-(use_num+1)]; //★左側に並べる数字の場合の数の総和★
				tmp %= MOD;
				tmp *= digit_sum[digit];
				tmp %= MOD;
				ret += tmp;
				ret %= MOD;
			}
		}
	}
	return ret;
}

int main(){

	//10の累乗を計算する
	POW[0] = 1;
	for(int i = 1; i < 801; i++){
		POW[i] = POW[i-1]*10;
		POW[i] %= MOD;
	}

	//ΣnPkおよびn!を求める
	ll number,tmp_sum;
	for(ll a = 199;a >= 0; a--){
		tmp_sum = a+1; //aP0 == 1,aP1 = a
		number = a;
		for(ll k = 1; k <= a-1; k++){
			number *= (a-k);
			number %= MOD;
			tmp_sum += number;
			tmp_sum %= MOD;
		}
		mult_num[a] = number; //a!
		mult_sum[a] = tmp_sum; //ΣaPk
	}

	//コンビネーションを求める
	nCm[0][0] = 1;
	for(int n = 1; n < 200; n++) {
		for (int k = 0; k <= n; k++) {
			if(k > 0){
				nCm[n][k] = nCm[n-1][k]+nCm[n-1][k-1];
			}else{ //k == 0
				nCm[n][k] = 1;
			}
			nCm[n][k] %= MOD;
		}
	}

	mult_num[0] = 1; //0! = 1

	zero_FLG = false; //0が登場したかどうかのフラグ
	for(int i = 1; i <= 4; i++){
		num_count[i] = 0;
		digit_sum[i] = 0;
	}

	scanf("%d",&N);

	int tmp_digit;
	ll tmp;

	for(int i = 0; i < N; i++){
		scanf("%lld",&tmp);
		if(tmp == 0){
			zero_FLG = true;
		}
		tmp_digit = get_digit(tmp);
		num_count[tmp_digit]++; //tmp_digit桁の数の個数を計上
		digit_sum[tmp_digit] += tmp; //tmp_digit桁の数の総和を求める
	}

	ll ans = calc();
	if(zero_FLG){
		N--; //0は入力されても最大1つ(問題仕様)
		num_count[1]--;
		ans -= calc();
		if(ans < 0)ans += MOD;
	}

	printf("%lld\n",ans);

	return 0;
}


```