#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int h, w;

const long long MOD = 1000000;

// 状態を表す文字列を正規化
void normalize(string& s)
{
    int m = 0;
    vector<char> change(w/2, ' ');

    for(int i=0; i<=w; ++i){
        if(isalpha(s[i]) && s[i] != 'A'){
            if(change[s[i]-'B'] == ' '){
                change[s[i]-'B'] = 'B' + m;
                ++ m;
            }
            s[i] = change[s[i]-'B'];
        }
    }
}

int main()
{
    cin >> h >> w;

    string init = 'A' + string(w, '.');
    map<string, long long> curr;
    curr[init] = 1;

    for(int y=0; y<=h; ++y){
        for(int x=0; x<=w; ++x){
            map<string, long long> next;

            if(x < w){
                for(map<string, long long>::iterator it=curr.begin(); it!=curr.end(); ++it){
                    string s = it->first;
                    if(s[0] != '*'){
                        string t = s.substr(1) + s[0];

                        if(isalpha(s[0]) && isalpha(s[1])){ // 上にある端点と左にある端点を結ぶ
                            if(s[0] != s[1]){
                                replace(t.begin(), t.end(), max(s[0], s[1]), min(s[0], s[1]));
                                t[0] = '*';
                                t[w] = '.';
                                normalize(t);
                                (next[t] += it->second) %= MOD;
                            }
                        }else if(isalpha(s[0])){            // 上にある端点を現在の位置の左に伸ばす
                            t[0] = t[w];
                            t[w] = '.';
                            normalize(t);
                            (next[t] += it->second) %= MOD;
                        }else if(isalpha(s[1])){            // 左にある端点を現在の位置に伸ばす
                            t[w] = t[0];
                            t[0] = '*';
                            normalize(t);
                            (next[t] += it->second) %= MOD;
                        }else{                              // 新たな線を追加する
                            t[0] = t[w] = 'A' + w / 2;
                            normalize(t);
                            (next[t] += it->second) %= MOD;
                        }
                    }else{
                        s[0] = '.';
                    }

                    string t = s.substr(1) + s[0];
                    (next[t] += it->second) %= MOD;
                }
            }else{ // 右端の場合の処理
                for(map<string, long long>::iterator it=curr.begin(); it!=curr.end(); ++it){
                    string s = it->first;
                    s = s.substr(1) + s[0];
                    if(s[w] == '*')
                        s[w] = '.';
                    normalize(s);
                    (next[s] += it->second) %= MOD;
                }
            }

            curr.swap(next);
        }
    }

    cout << curr[string(w, '.')+'A'] << endl;

    return 0;
}

Measured memory_bytes: 1228