#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;
ifstream in ("div4.in");
ofstream out ("div4.out");
#define MAX(a , b) ((a < b) ? b : a)

int const nmax = 100000;
int const modulo = 1000003;
int fact[5 + nmax];
char line[5 + nmax];
void gcd(int a , int b , int &x ,int &y){
  if(b == 0){
    x = 1;
    y = 0;
  } else{
    gcd(b , a % b , x , y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
  }
}
void computefact(){
  fact[0] = 1;
  for(int i = 1 ; i <= nmax ;i++){
    fact[i] = (1LL * fact[i - 1] * i) % modulo;
  }
}
int comb(int n ,int k){
  if(n == -1)
    return 1;
  int result = fact[n];
  int result2 = (1LL * fact[n - k] * fact[k]) % modulo;
  int x , y;
  gcd(result2 , modulo , x , y);
  x %= modulo;
  if(x < 0)
    x += modulo;
  result = (1LL * result * x) % modulo;
  return result;
}
int n , k;

int main()
{
  computefact();
  line[0] = '0';
  in>>(line + 1);
  n = strlen(line + 1);
  in>>k;
  int start = MAX(0 , n - (k + 2) + 1);
  int even = 0, odd = 0;
  int result = 0;
  for(int i = start ;i <= n ;i++){
    int a = line[i] - '0';
    if(a % 2 == 0){
      if(a % 4 == 0){
        result += even;
      } else
        result += odd;
      if(modulo <= result)
        result -= modulo;
    }
    if(a % 2 == 0){
      even += comb(i - 1 , i - start);
      if(modulo <= even)
        even -= modulo;
    } else{
      odd += comb(i - 1 , i - start);
      if(modulo <= odd)
        odd -= modulo;
    }
  }
  out<<result;
  return 0;
}