1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
typedef long long LL;
const int N = 20;
const int mod = 1000000007;
LL F[N], dp[N][210], cnt[N][210];
void init(){
    memset(dp,0,sizeof(dp));
    memset(cnt,0,sizeof(cnt));
    F[0] = 0;
    F[1] = 1;
    for(int i=2; i<N; i++)  F[i] = (F[i-1]*10)%mod;
    for(int i=0; i<10; i++){
        dp[1][i+100] = i;
        cnt[1][i+100] = 1;
    }
    for(int i=2; i<N-1; i++){
        for(int j=0; j<=200; j++){
            for(int k=0; k<10; k++){
                int x = k-j+200;
                LL tmp = ((F[i]*k)%mod * cnt[i-1][j] + dp[i-1][j])%mod;
                dp[i][x] = (dp[i][x] + tmp)%mod;
                cnt[i][x] = (cnt[i][x] + cnt[i-1][j])%mod;
            }
        }
    }
}
LL sum(LL x, int k){
    if(x<=0)    return 0;
    if(x<10){
        if(x==k)    return x;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX