#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
using namespace std;
typedef long long ll;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
string s;
int a[55],n;
ll comb[55][55];
int dp[55],tmp[55];
int ti[10];
ll ans;
int tbl[]={0,45,615,6570,63657,597600,5689830,56017680,564676515,706253855,53001921,116607642,807754616,555253686,93648429,358785453,214810078,642432049,158594480,599067452,311948107,103373398,86116420,524897403,907977314,138576683,44283636,241998094,583822532,537947530,636674358,585550280,414900917,756538572,442412153,703712200,837470764,311869987,733194120,596841112,387537647,769854984,977490984,112225690,117109110,439421821,374895741,471922812,10030060,835556902,25251932};
void dfs(int pos,int flag){
    if(pos==0){
        int x=0;
        for(int i=1;i<=9;i++)if(ti[i]>=ti[x])x=i;
        ans+=x;
        return;
    }
    if(!flag){
        int ma=0,N=pos;
        for(int i=0;i<=9;i++)ma=max(ma,ti[i]),N+=ti[i];
        for(int x=1;x<=9;x++){
            for(int y=0;y<=pos;y++){
                if(ti[x]+y<ma)continue;
                if((ti[x]+y)*(x+1)+(ti[x]+y-1)*(9-x)<N)continue;
                fill(dp,dp+1+pos,0);
                dp[y]=comb[pos][y];
                for(int i=0;i<=9;i++){
                    if(i==x)continue;
                    fill(tmp,tmp+1+pos,0);
                    bool flag=1;
                    for(int j=0;j+y<=pos;j++){
                        int de=j+ti[i]-(y+ti[x]);
                        if(de>0||(x<i&&de==0))break;
                        for(int k=j;k<=pos;k++){
                            tmp[k]=(tmp[k]+dp[k-j]*comb[pos-k+j][j])%MOD;
                        }
                    }
                    swap(tmp,dp);
                }
                ans+=(ll)x*dp[pos];
            }
        }
        ans%=MOD;
        return;
    }
    int ed=flag?a[pos]:9;
    for(int i=0;i<=ed;i++){
        ti[i]++;
        dfs(pos-1,flag&&i==ed);
        ti[i]--;
    }
}
void solve(){
    ans=0;
    cin>>s;
    n=s.size();
    ans=tbl[n-1];
    for(int i=1;i<=n;i++)a[i]=s[n-i]-'0';
    for(int i=1;i<=a[n];i++){
        ti[i]++;
        dfs(n-1,i==a[n]);
        ti[i]--;
    }
    cout<<ans<<"\n";
}
int main()
{
    for(int i=0;i<=50;i++){
        comb[i][0]=1;
        for(int j=1;j<=i;j++){
            comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%MOD;
        }
    }
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}