#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 201;

ll mod_pow(ll a,ll b)
{
    a %= MOD;
    ll res = 1;
    while(b){
        if(b & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = fac[i-1] * (ll) i % MOD;
		finv[i] = finv[i-1] * inv[i] % MOD;
	}
}

void extgcd(int a,int b, int& x,int& y)
{
	if(b != 0){
		extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
}

int mod_inverse(int a,int m)
{
	int x,y;
	extgcd(a,m,x,y);
	return (m + x % m) % m;
}

ll add(ll x,ll y)
{
    return (x + y)%MOD;
}

ll sub(ll x,ll y)
{
    return (x+MOD-y)%MOD;
}

ll mul(ll x,ll y)
{
    return x*y%MOD;
}

int dp[201][801];
int dp2[201][801];
int ten[801],smpow[201];

int solve(vi& vec,vi&d,int n){
    rep(j,n+1){
        rep(k,801){
            dp[j][k] = 0;
        }
    }
    dp[0][0] = 1;
    rep(i,n){
        rrep(j,i+1){
            rep(k,801){
                if(dp[j][k]){
                    dp[j+1][k+d[i]] = add(dp[j+1][k+d[i]],dp[j][k]);
                }
            }
        }
    }
    ll ans = 0;
    rep(i,n){
        if(vec[i]){
            rep(j,n+1){
                rep(k,801){
                    dp2[j][k] = dp[j][k];
                }
            }
            rep(j,n){
                srep(k,d[i],801){
                    if(dp2[j][k-d[i]]){
                        dp2[j+1][k] = sub(dp2[j+1][k],dp2[j][k-d[i]]);
                    }
                }
            }
            rep(j,n){
                rep(k,801){
                    if(dp2[j][k]){
                        ans = add(ans,mul(mul(mul(dp2[j][k],smpow[n-j]),mul(ten[k],vec[i])),fac[j]));
                    }
                }
            }
        }
    }
    return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi vec(n),d(n,0);
    ten[0] = 1;
    rep(i,801){
        ten[i+1] = mul(ten[i],10);
    }
    make();
    smpow[0] = 1;
    rep(i,n){
        rep(j,i+1){
            smpow[i+1] = add(smpow[i+1],mul(fac[i],finv[j]));
        }
    }
    bool flag = false;
    rep(i,n){
        cin >> vec[i];
        if(vec[i] == 0){
            flag = true;
        }
        int temp = vec[i];
        if(temp){
            while(temp){
                ++d[i];
                temp /= 10;
            }
        }else{
            ++d[i];
        }
    }
    int r1 = solve(vec,d,n),r2 = 0;
    if(flag){
        vi w,e;
        rep(i,n){
            if(vec[i]){
                w.pb(vec[i]),e.pb(d[i]);
            }
        }
        r2 = solve(w,e,n-1);
    }
    cout << sub(r1,r2) << "\n";
    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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 201;

ll mod_pow(ll a,ll b)
{
    a %= MOD;
    ll res = 1;
    while(b){
        if(b & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = fac[i-1] * (ll) i % MOD;
		finv[i] = finv[i-1] * inv[i] % MOD;
	}
}

void extgcd(int a,int b, int& x,int& y)
{
	if(b != 0){
		extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
}

int mod_inverse(int a,int m)
{
	int x,y;
	extgcd(a,m,x,y);
	return (m + x % m) % m;
}

ll add(ll x,ll y)
{
    return (x + y)%MOD;
}

ll sub(ll x,ll y)
{
    return (x+MOD-y)%MOD;
}

ll mul(ll x,ll y)
{
    return x*y%MOD;
}

int dp[201][801];
int dp2[201][801];
int ten[801],smpow[201];

int solve(vi& vec,vi&d,int n){
    rep(j,n+1){
        rep(k,801){
            dp[j][k] = 0;
        }
    }
    dp[0][0] = 1;
    rep(i,n){
        rrep(j,i+1){
            rep(k,801){
                if(dp[j][k]){
                    dp[j+1][k+d[i]] = add(dp[j+1][k+d[i]],dp[j][k]);
                }
            }
        }
    }
    ll ans = 0;
    rep(i,n){
        if(vec[i]){
            rep(j,n+1){
                rep(k,801){
                    dp2[j][k] = dp[j][k];
                }
            }
            rep(j,n){
                srep(k,d[i],801){
                    if(dp2[j][k-d[i]]){
                        dp2[j+1][k] = sub(dp2[j+1][k],dp2[j][k-d[i]]);
                    }
                }
            }
            rep(j,n){
                rep(k,801){
                    if(dp2[j][k]){
                        ans = add(ans,mul(mul(mul(dp2[j][k],smpow[n-j]),mul(ten[k],vec[i])),fac[j]));
                    }
                }
            }
        }
    }
    return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi vec(n),d(n,0);
    ten[0] = 1;
    rep(i,801){
        ten[i+1] = mul(ten[i],10);
    }
    make();
    smpow[0] = 1;
    rep(i,n){
        rep(j,i+1){
            smpow[i+1] = add(smpow[i+1],mul(fac[i],finv[j]));
        }
    }
    bool flag = false;
    rep(i,n){
        cin >> vec[i];
        if(vec[i] == 0){
            flag = true;
        }
        int temp = vec[i];
        if(temp){
            while(temp){
                ++d[i];
                temp /= 10;
            }
        }else{
            ++d[i];
        }
    }
    int r1 = solve(vec,d,n),r2 = 0;
    if(flag){
        vi w,e;
        rep(i,n){
            if(vec[i]){
                w.pb(vec[i]),e.pb(d[i]);
            }
        }
        r2 = solve(w,e,n-1);
    }
    cout << sub(r1,r2) << "\n";
    return 0;
}
```