// Arup Guha
// 7/14/2013
// Solution to 2009 South East Regional Problem I: Mosaic

import java.util.*;

public class i {

	public final static int MOD = 1000000;
	public final static int MAX = 500;

	public static void main(String[] args) {

		int[][][] maskLookUp = new int[9][][];

		// Build our lookup tables.
		// These are 9 separate 2D tables for sizes 2 through 10.
		// Each 2D table, in index [i,j] stores how many ways you can start with a grid in bitmask i in the
		// first row and end up with bitmask j in the second row.
		for (int i=0; i<9; i++) {
			int n = i+2;
			int size = 1 << n;
			maskLookUp[i] = new int[size][size];
			fill(maskLookUp[i], n);
		}

		// Build answers.
		int[][] ans = new int[9][];
		for (int i=0; i<9; i++)
			ans[i] = solve(i+2, maskLookUp[i]);


		Scanner stdin = new Scanner(System.in);
		int row = stdin.nextInt() - 2;
		int col = stdin.nextInt();

		// Answer all queries, by looking up answer in table.
		while (col != 0) {
			System.out.println(ans[row][col]);
			row = stdin.nextInt() - 2;
			col = stdin.nextInt();
		}

	}

	// Returns all solutions for input size n rows, with the appropriate bitmask lookup table.
	public static int[] solve(int n, int[][] maskLookUp) {

		int[][] table = new int[MAX+1][1 << n];

		// Stands for empty board.
		table[0][0] = 1;

		// i is the current column we're filling.
		for (int i=1; i<MAX; i++) {

			// Go through all previous bitmasks.
			for (int j=0; j<table[i-1].length; j++) {

				// Here is one we can build off.
				if (table[i-1][j] > 0)

					// Find all the transitions from bitmask j to bitmask k, for all k.
					for (int k=0; k<maskLookUp.length; k++)
						table[i][k] = (table[i][k] + table[i-1][j]*maskLookUp[j][k])%MOD;
			}

			// Conceptually, having a full row in column i is the same as having an empty row in column i+1.
			table[i+1][0] = table[i][(1<<n)-1];
		}

		// Copy over the answers we care about and return.
		int[] ans = new int[MAX+1];
		for (int i=2; i<ans.length; i++)
			ans[i] = table[i-1][(1<<n) - 1];

		return ans;
	}

	// Fills the maskTable function for input size n rows.
	public static void fill(int[][] maskTable, int n) {

		int size = maskTable.length;

		// i is the mask for items filled in, in the last column.
		for (int i=0; i<maskTable.length-1; i++) {
			fillRow(maskTable[i], i, n);
		}
	}

	// Fills the row mask in the function of size n in the array maskRow.
	public static void fillRow(int[] maskRow, int mask, int n) {

		boolean[][] grid = new boolean[n][2];
		int temp = mask;

		// Fill in used squares in first column based on mask.
		int i = 0;
		while (temp > 0) {
			if ((temp & 1) > 0)
				grid[i][0] = true;
			i++;
			temp = temp >> 1;
		}

		// Recursively try all ways to fill in this grid.
		fillRec(maskRow, grid);
	}

	// Returns first row in column 0 that the grid is unfilled(false).
	public static int filled(boolean[][] grid) {
		int i = 0;
		while (i<grid.length && grid[i][0]) i++;
		return i;
	}

	// Returns the mask of the second column of grid.
	public static int getMask(boolean[][] grid) {

		int bitVal = 1, mask = 0;
		for (int i=0; i<grid.length; i++) {
			if (grid[i][1]) mask += bitVal;
			bitVal = bitVal << 1;
		}

		return mask;
	}

	// Recursively fills grid in all possible ways, marking in maskRow, each possible outcome.
	// Initial call needs to have the first column of grid filled in with the desired starting mask.
	public static void fillRec(int[] maskRow, boolean[][] grid) {

		// Find first unfilled spot.
		int i = filled(grid);

		// If we're done, mark this arrangement.
		if (i == grid.length) {
			maskRow[getMask(grid)]++;
			return;
		}

		// Do four pieces that need 2 more rows...
		if (i < grid.length-1) {

			// Try square piece.
			if (!grid[i+1][0] && !grid[i][1] && !grid[i+1][1]) {
				grid[i][0] = true; grid[i+1][0] = true; grid[i][1] = true; grid[i+1][1] = true;
				fillRec(maskRow, grid);
				grid[i][0] = false; grid[i+1][0] = false; grid[i][1] = false; grid[i+1][1] = false;
			}

			// Try flipped L.
			if (!grid[i+1][0] && !grid[i][1]) {
				grid[i][0] = true; grid[i+1][0] = true; grid[i][1] = true;
				fillRec(maskRow, grid);
				grid[i][0] = false; grid[i+1][0] = false; grid[i][1] = false;
			}

			// Try regular L.
			if (!grid[i+1][0] && !grid[i+1][1]) {
				grid[i][0] = true; grid[i+1][0] = true; grid[i+1][1] = true;
				fillRec(maskRow, grid);
				grid[i][0] = false; grid[i+1][0] = false; grid[i+1][1] = false;
			}

			// Try L flipped over both axes.
			if (!grid[i][1] && !grid[i+1][1]) {
				grid[i][0] = true; grid[i][1] = true; grid[i+1][1] = true;
				fillRec(maskRow, grid);
				grid[i][0] = false; grid[i][1] = false; grid[i+1][1] = false;
			}

		}

		// Try L flipped on vertical axis. Valid on last row, not first.
		if (i > 0 && !grid[i-1][1] && !grid[i][1]) {
			grid[i][0] = true; grid[i][1] = true; grid[i-1][1] = true;
			fillRec(maskRow, grid);
			grid[i][0] = false; grid[i][1] = false; grid[i-1][1] = false;
		}
	}
}