#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007 ;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
const long double epsA=1e-4;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint solve(array<llint,5>in){
	static llint dp[201][201];
	static llint ep[201][201];
	dp[0][0]=1;ep[0][0]=1;
	int h,i=0,j,k,aa=1;
	for(h=1;h<=4;h++){
		aa*=10;
		for(k=1;k<=in[h];k++){
			i++;
			dp[i][0]=dp[i-1][0];
			ep[i][0]=ep[i-1][0];
			dp[i-1][i]=0;ep[i-1][i]=0;
			for(j=1;j<=i;j++){
				dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*j)%mod;
				ep[i][j]=(ep[i-1][j]+ep[i-1][j-1]*j*aa)%mod;
			}
		}
		//cerr<<"de"<<__LINE__<<endl;
	}
	int n=in[1]+in[2]+in[3]+in[4];
	//cerr<<"n="<<n<<endl;
	llint ue[201]={};
	llint st[201]={};
	for(i=0;i<=n;i++){
		//cerr<<"de"<<__LINE__<<endl;
		for(j=0;j<=i;j++){ue[i]+=dp[i][j];}
		ue[i]%=mod;
		//cerr<<"i="<<i<<"ue="<<ue[i]<<"st="<<st[i]<<endl;
	}
	llint ans=0;
	for(i=0;i<=n;i++){ans+=ue[i]*ep[n][n-i];ans%=mod;}
	//cerr<<"ans="<<ans<<endl;
	return ans;
	
}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	
	llint n;cin>>n;
	//桁数、数字
	//何桁目に来ることがどのくらいあるか
	//桁数 1,2,3,4の4パターンしかない
	//自分より上 m枚まである->dpする
	//0はじめ対策 何とかする
	array<llint,5>mai={},suu={};
	bool Oaru=false;
	int h,i,j;
	for(i=0;i<n;i++){
		int a;cin>>a;
		if(a==0){mai[1]++;Oaru=true;}
		int k=1,kk=0;
		while(k<=a){k*=10;kk++;}
		mai[kk]++;suu[kk]+=a;
	}
	llint ans=0;
	for(h=1;h<=4;h++){
		if(mai[h]==0){continue;}
		mai[h]--;
		ans+=solve(mai)*suu[h];
		if(Oaru&&mai[1]>0){
			mai[1]--;
			ans-=solve(mai)*suu[h];
			mai[1]++;
		}
		ans%=mod;
		mai[h]++;
	}
	ans%=mod;ans+=mod;ans%=mod;
	cout<<ans<<endl;
	return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007 ;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
const long double epsA=1e-4;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint solve(array<llint,5>in){
	static llint dp[201][201];
	static llint ep[201][201];
	dp[0][0]=1;ep[0][0]=1;
	int h,i=0,j,k,aa=1;
	for(h=1;h<=4;h++){
		aa*=10;
		for(k=1;k<=in[h];k++){
			i++;
			dp[i][0]=dp[i-1][0];
			ep[i][0]=ep[i-1][0];
			dp[i-1][i]=0;ep[i-1][i]=0;
			for(j=1;j<=i;j++){
				dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*j)%mod;
				ep[i][j]=(ep[i-1][j]+ep[i-1][j-1]*j*aa)%mod;
			}
		}
		//cerr<<"de"<<__LINE__<<endl;
	}
	int n=in[1]+in[2]+in[3]+in[4];
	//cerr<<"n="<<n<<endl;
	llint ue[201]={};
	llint st[201]={};
	for(i=0;i<=n;i++){
		//cerr<<"de"<<__LINE__<<endl;
		for(j=0;j<=i;j++){ue[i]+=dp[i][j];}
		ue[i]%=mod;
		//cerr<<"i="<<i<<"ue="<<ue[i]<<"st="<<st[i]<<endl;
	}
	llint ans=0;
	for(i=0;i<=n;i++){ans+=ue[i]*ep[n][n-i];ans%=mod;}
	//cerr<<"ans="<<ans<<endl;
	return ans;
	
}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	
	llint n;cin>>n;
	//桁数、数字
	//何桁目に来ることがどのくらいあるか
	//桁数 1,2,3,4の4パターンしかない
	//自分より上 m枚まである->dpする
	//0はじめ対策 何とかする
	array<llint,5>mai={},suu={};
	bool Oaru=false;
	int h,i,j;
	for(i=0;i<n;i++){
		int a;cin>>a;
		if(a==0){mai[1]++;Oaru=true;}
		int k=1,kk=0;
		while(k<=a){k*=10;kk++;}
		mai[kk]++;suu[kk]+=a;
	}
	llint ans=0;
	for(h=1;h<=4;h++){
		if(mai[h]==0){continue;}
		mai[h]--;
		ans+=solve(mai)*suu[h];
		if(Oaru&&mai[1]>0){
			mai[1]--;
			ans-=solve(mai)*suu[h];
			mai[1]++;
		}
		ans%=mod;
		mai[h]++;
	}
	ans%=mod;ans+=mod;ans%=mod;
	cout<<ans<<endl;
	return 0;
}

```