// Arup Guha
// 11/17/2014
// Solution to South East Regional D1 Problem: Knights

import java.util.*;

public class knights {

	final public static long MOD = 1000000009L;

	public static void main(String[] args) {

		// Get input.
		Scanner stdin = new Scanner(System.in);
		int r = stdin.nextInt();
		int c = stdin.nextInt();

		// Easy cases.
		if (r == 1) System.out.println(modPow(2,c));
		else if (c == 1) System.out.println(modPow(2,r));

		// Typical case with matrix.
		else {

			// Build our matrix.
			long[][] m = buildM(r);

			// Get exponent for it.
			long exp = c - 2;

			// Exponentiate.
			long[][] res = fastMatExpoMod(m,exp);

			// Need to add all entries (alternative to multiplying res by column of 1s.)
			long finalres = 0;
			for (int i=0; i<res.length; i++)
				for (int j=0; j<res[0].length; j++)
					finalres = (finalres + res[i][j])%MOD;

			// We're done!
			System.out.println(finalres);
		}
	}

	// Returns base^exp mod MOD.
	public static long modPow(long base, long exp) {
		if (exp == 0L) return 1L;
		if (exp%2L == 0L) {
			long sqrt = modPow(base, exp/2);
			return (sqrt*sqrt)%MOD;
		}
		return (modPow(base,exp-1)*base)%MOD;
	}

	public static long[][] buildM(int r) {

		// Will store all valid masks - both ways.
		ArrayList<Integer> masks = new ArrayList<Integer>();
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

		// Try all arrangements of knights on the last two columns.
		for (int i=0; i<(1 << (2*r)); i++) {
			if (valid(i >> r, i & ((1 << r) - 1) )) {
				map.put(i, masks.size());
				masks.add(i);
			}
		}

		// Now, set up matrix.
		int n = masks.size();
		long[][] ans = new long[n][n];

		// See where each transition can go - i is the setting of knights on the last two rows.
		for (int i=0; i<n; i++) {

			int mask = masks.get(i);
			int r1Mask = mask >> r;
			int r2Mask = mask & ((1 << r) - 1);

			// j is the possible mask for the next row
			for (int j=0; j<(1 << r); j++) {

				// See if this set of three columns is valid.
				if (valid(r1Mask, r2Mask , j))
					ans[i][map.get((r2Mask << r) + j)] = 1L;
			}
		}

		return ans;
	}

	// Fast Matrix Expo
	public static long[][] fastMatExpoMod(long[][] m,long exp) {
		int n = m.length;
		if (exp == 0L) return identity(n);
		if (exp%2 == 0L) {
			long[][] res = fastMatExpoMod(m,exp/2);
			return mult(res, res);
		}
		return mult(fastMatExpoMod(m,exp-1), m);
	}

	// Returns an n x n identity matrix.
	public static long[][] identity(int n) {
		long[][] ans = new long[n][n];
		for (int i=0; i<n; i++)
			ans[i][i] = 1L;
		return ans;
	}

	public static long[][] mult(long[][] a, long[][] b) {

		// Set up matrix.
		int n = a.length;
		long[][] res = new long[n][n];

		// Multiply and mod.
		for (int i=0; i<n; i++)
			for (int j=0; j<n; j++)
				for (int k=0; k<n; k++)
					res[i][j] = (res[i][j] + a[i][k]*b[k][j])%MOD;

		// Return.
		return res;
	}

	public static boolean valid(int r1Mask, int r2Mask) {

		// Anything goes in first two rows.
		if (r1Mask < 4 && r2Mask < 4) return true;

		// Check next two rows.
		for (int i=4,j=1; i<=8; i*=2,j*=2) {
			if ((r1Mask & i) > 0 && (r2Mask & j) > 0) return false;
			if ((r2Mask & i) > 0 && (r1Mask & j) > 0) return false;
		}

		// Made it!
		return true;
	}

	// Assume r1Mask, r2Mask is already valid.
	public static boolean valid(int r1Mask, int r2Mask, int r3Mask) {

		// Check bit on each row of column 3.
		for (int i=0; i<4; i++) {

			// Not a knight here.
			if ((r3Mask & (1 << i)) == 0) continue;

			// Conflicting knight in column 2;
			if (i>1 && (r2Mask & (1 << (i-2))) > 0) return false;
			if (i<2 && (r2Mask & (1 << (i+2))) > 0) return false;

			// Conflicting knight in column 1.
			if (i>0 && (r1Mask & (1 << (i-1))) > 0) return false;
			if (i<3 && (r1Mask & (1 << (i+1))) > 0) return false;
		}

		// If we get here, we're good.
		return true;
	}
}