fork(1) download
#include<iostream>
#include<string>
using namespace std;
#define MAX_N 110
#define MAX_D 120000
string S; int D; int num[MAX_N][10]; int dp[MAX_N][MAX_D];
int main() {
	cin >> S >> D;
	for (int i = 0; i < S.size(); i++) {
		for (int j = 1; j < 10; j++) {
			if (i + j <= S.size()) {
				string T = S.substr(i, j);
				int M = stoi(T);
				num[i][j] = M;
			}
			else {
				num[i][j] = (1 << 30);
			}
		}
	}
	dp[0][0] = 1;
	for (int i = 1; i <= S.size(); i++) {
		for (int j = 0; j <= D; j++) {
			for (int k = 1; k < 10; k++) {
				if(i - k < 0){continue;}
				int target = j - num[i - k][k];
				if (target < 0) { continue; }
				dp[i][j] += dp[i - k][target];
				dp[i][j] %= 1000000007;
			}
		}
	}
	int sum = 0;
	for (int j = 0; j <= D; j++) {
		sum += dp[S.size()][j]; sum %= 1000000007;
	}
	cout << sum << endl;
	return 0;
}
Success #stdin #stdout 0s 55032KB
stdin
1355
50
stdout
3