Contests

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<utility>

using namespace std;

const int64_t MOD=1000000007;

int64_t power_mod(int64_t a, int64_t k, int64_t m) {
  if(k == 0) return 1;
  int64_t res=power_mod(a, k/2, m);
  if(k%2 == 0) return res*res%m;
  return a*res%m*res%m;
}

int64_t binomial(int64_t m, int64_t n) {
  int64_t prod=1;
  for(int64_t i=m-n+1;i<=m;i++) {
    prod*=i;
    prod%=MOD;
  }
  for(int64_t i=1;i<=n;i++) {
    prod*=power_mod(i,MOD-2,MOD);
    prod%=MOD;
  }
  return prod;
}

int main(void) {
  int64_t n,s;
  cin >> n >> s;
  int64_t empties=0;
  for(int64_t i=0;i<n;i++) {
    string st;
    cin >> st;
    if(st.size() == 1) {
      if(st[0] == '?') {
        empties++;
      } else {
        int64_t foo=st[0]-'0';
        s-=foo;
      }
    } else {
      int64_t foo=10*(st[0]-'0') + st[1]-'0';
      s-=foo;
    }
  }
  int64_t total=0;
  for(int64_t m=0;11*m<=s;m++) {
    int64_t u=s - 11*m;
    int64_t blah=binomial(u+empties-1,empties-1)*binomial(empties, m)%MOD;
    if(m%2) total-=blah;
    else total+=blah;
    total%=MOD;
  }
  if(total < 0) total+=MOD;
  cout << total << endl;
  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