/*
M == 1
  10 -> START

  10 -> 10, 01
  01 -> 10, 01

  GOAL -> 01

M == 2
  100 -> START

  001 -> 001, 010, 100, 111L
  010 -> 001, 010, 100
  100 -> 001, 010, 100, 111R
  111L-> 100, 111L
  111R-> 001, 111R

  GOAL -> 001
*/

#include <iostream>

using namespace std;
const long MOD = 1000000;
enum SET {
  oox, oxo, xoo, xxxL, xxxR
};

bool canTravel[5][5] = {
  {true, true, true, true, false},
  {true, true, true, false, false},
  {true, true, true, false, true},
  {false, false, true, true, false},
  {true, false, false, false, true}
};

long solve1(int N);
long solve2(int N);

int main() {
  int N,M;
  cin >> N >> M;
  long ans;
  if (M==1) {
    ans = solve1(N);
  } else {
    ans = solve2(N);
  }
  cout << ans << endl;
  return 0;
}

long solve1(int N) {
  long ans = 1;
  for (int i=0; i<N; ++i) {
    ans *= 2;
    ans %= MOD;
  }
  return ans;
}
long solve2(int N) {
  long ans = 0;
  long dp[101][5] = {{0}};
  dp[0][(SET)xoo] = 1;
  for (int i=1; i<=N; ++i) {
    for (int jfrom=0; jfrom<5; ++jfrom) {
      for (int j2=0; j2<5; ++j2) {
        if (canTravel[jfrom][j2]) {
          dp[i][j2] += dp[i-1][jfrom];
          dp[i][j2] %= MOD;
        }
      }
    }
  }

  for (int jfrom=0; jfrom<5; ++jfrom) {
    SET j2 = oox;
    if (canTravel[jfrom][j2]) {
      ans += dp[N][jfrom];
      ans %= MOD;
    }
  }
  return ans;
}