eqpfeH - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define len(v) (int)(v).size()
#define loop(i, l, r)                                                          \
  for (int(i) = (l); (r) > (l) ? (i) < (r) : (i) > (r);                        \
       (r) > (l) ? (i)++ : (i)--)
#define SuperSonic ios::sync_with_stdio(false), cin.tie(nullptr)

const int MOD = 1e9 + 7;

ll add(ll a, ll b) { return (a % MOD + b % MOD) % MOD; }

ll mult(ll a, ll b) { return (a % MOD * b % MOD) % MOD; }

ll sub(ll a, ll b) { return (a % MOD - b % MOD + MOD) % MOD; }

ll fp(ll base, ll power) {
  if (power == 0)
    return 1;

  ll hp = fp(base, power / 2);
  ll fullPower = mult(hp, hp);

  if (power % 2 != 0)
    fullPower = mult(fullPower, base);

  return fullPower;
}

ll divi(ll a, ll b) { return mult(a, fp(b, MOD - 2)); }

void solve() {
  ll n, k;
  cin >> n >> k;

  string s;
  cin >> s;

  vector<int> zf;
  ll ans{}, series = divi(sub(fp(2, k * n), 1), sub(fp(2, n), 1)), ZFCurBlock{},
            ZFNextBlock{};
  loop(i, 0, n) {
    if (s[i] == '0' || s[i] == '5') {
      ans = add(ans, mult(fp(2, i), series));
      zf.push_back(i);
      ZFCurBlock = add(ZFCurBlock, fp(2, i));
    }
  }

  ll kSeries = divi(sub(mult(series, fp(2, n)), k), sub(fp(2, n), 1)),
     prevKSeries = sub(kSeries, series);
  for (int i : zf) {
    ZFCurBlock = sub(ZFCurBlock, fp(2, i));
    ZFNextBlock = add(ZFNextBlock, fp(2, i + n));

    if (s[i] == '0') {
      ans = sub(ans, mult(kSeries, divi(ZFCurBlock, fp(2, i + 1))));
      ans = sub(ans, mult(prevKSeries, divi(ZFNextBlock, fp(2, i + 1))));
    }
  }

  cout << ans;
}

int main() {
  SuperSonic;

  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
}