#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i) {
    if (i != v.begin()) o << ", ";
    o << (*i);
  }
  o << "]";
  return o;
}
template <class T>
ostream& operator<<(ostream& o, const set<T>& s) {
  o << "{";
  for (typename set<T>::const_iterator i = s.begin(); i != s.end(); ++i) {
    if (i != s.begin()) o << ", ";
    o << (*i);
  }
  o << "}";
  return o;
}
template <class K, class V>
ostream& operator<<(ostream& o, const map<K, V>& m) {
  o << "{";
  for (typename map<K, V>::const_iterator i = m.begin(); i != m.end(); ++i) {
    if (i != m.begin()) o << ", ";
    o << i->first << ":" << i->second;
  }
  o << "}";
  return o;
}
template <class T>
ostream& operator<<(ostream& o, const vector<vector<T> >& m) {
  o << "[\n";
  for (typename vector<vector<T> >::const_iterator i = m.begin(); i != m.end();
       ++i) {
    o << "  " << (*i);
    o << (i + 1 != m.end() ? ",\n" : "\n");
  }
  o << "]\n";
  return o;
}
string bitstr(int n, int d = 0) {
  string r;
  for (int i = 0; i < d || n > 0; ++i, n >>= 1) {
    r += (n & 1) ? "1" : "0";
  }
  reverse(r.begin(), r.end());
  return r;
}
const int MOD = 1000000007;
vector<vector<int> > E(size_t n) {
  vector<vector<int> > r(n, vector<int>(n));
  for (size_t i = 0; i < n; i++) r[i][i] = 1;
  return r;
}
vector<vector<int> > operator*(const vector<vector<int> >& x,
                               const vector<vector<int> >& y) {
  assert(x[0].size() == y.size());
  vector<vector<int> > r(x.size(), vector<int>(y[0].size()));
  for (size_t i = 0; i < r.size(); i++)
    for (size_t j = 0; j < r[0].size(); j++)
      for (size_t k = 0; k < y.size(); k++)
        r[i][j] = (r[i][j] + (long long)x[i][k] * y[k][j]) % MOD;
  return r;
}
int main() {
  string a;
  int k;
  cin >> a >> k;
  vector<vector<int> > A = E(3);
  vector<vector<int> > Anot5 = E(3);
  Anot5[0][1] = Anot5[1][0] = 1;
  vector<vector<int> > A5 = Anot5;
  A5[0][2] = 1;
  for (int i = a.size() - 1; i >= 0; i--) {
    if ((a[i] - '0') % 5 == 0)
      A = A5 * A;
    else
      A = Anot5 * A;
  }
  vector<vector<int> > x(3, vector<int>(1));
  x[0][0] = 0;
  x[1][0] = 0;
  x[2][0] = 1;
  while (k) {
    if (k & 1) x = A * x;
    k >>= 1;
    A = A * A;
  }
  cout << (x[0][0] + x[1][0]) % MOD << endl;
}
