// Arup Guha
// 11/7/2018
// Solution to 2018 SER D1 Problem: Count the Bits

import java.util.*;

public class bits {
	
	final public static long MOD = 1000000009L;
	
	public static void main(String[] args) {
		
		// Get input.
		Scanner stdin = new Scanner(System.in);
		int k = stdin.nextInt();
		int pow = stdin.nextInt();
		
		// Pre-comp for each position bit value mod k.
		int[] pow2 = new int[pow+1];
		pow2[0] = 1%k;
		for (int i=1; i<=pow; i++)
			pow2[i] = (2*pow2[i-1])%k;
		
		// DP tables - submits[i][j] stores sum of all bits in vals = j%k < 2^i.
		long[][] sumbits = new long[pow+1][k];
		
		// freq[i][j] stores # of values = j%k < 2^i.
		long[][] freq = new long[pow+1][k];
		freq[0][0] = 1;
		
		// b is bit location.
		for (int bits=1; bits<=pow; bits++) {
			
			// This is the current mod.
			for (int mod=0; mod<k; mod++) {
				
				// Answers if we put 0 bit in location bits-1.
				long mybits = sumbits[bits-1][mod];
				long mycnt = freq[bits-1][mod];
				
				// If we have a 1 in this bit position, this is the mod for the rest of the bits.
				int othermod = (mod - pow2[bits-1] + k)%k;
				
				// So these are the relevant subcases when placing 1 in the msb.
				long otherbits = sumbits[bits-1][othermod];
				long othercnt = freq[bits-1][othermod];
				
				// These are the corresponding results.
				sumbits[bits][mod] = (mybits + otherbits + othercnt)%MOD;
				freq[bits][mod] = (mycnt + othercnt)%MOD;				
				
			} // end mod
		} // end bits.
	
		// Ta da!
		System.out.println(sumbits[pow][0]);
	}
}