Contests

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000000 + 7;

int strToInt(string s) {
  int m = 1;
  int sum = 0;
  while(!s.empty()) {
    sum += (s.back() - '0') * m;
    m *= 10;
    s.pop_back();
  }
  return sum;
}

ll dp[1010][110];

int main() {
  int n, sum;
  cin >> n >> sum;
  int t = 0;
  for(int i = 0; i < n; ++i) {
    string str;
    cin >> str;
    if(str[0] != '?') {
      sum -= strToInt(str);
    } else {
      ++t;
    }
  }
  if(t == 0) {
    cout << 1 << "\n";
    return 0;
  }
  for(int i = 0; i <= 10; ++i) {
    dp[i][1] = 1;
  }
  for(int x = 2; x <= t; ++x) {
    for(int y = 0; y <= 1001; ++y) {
      for(int y2 = y; y2 >= max(0, y - 10); --y2) {
	dp[y][x] += dp[y2][x - 1];
      }
      dp[y][x] %= MOD;
    }
  }
  cout << dp[sum][t] << "\n";
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED