#include <iostream>
using namespace std;
const int mod = 1000000009;

class Matrix {
private:
  int n;
  long long **matrix;
public:
  Matrix() {
    n = 0;
    matrix = nullptr;
  }
  ~Matrix();
  Matrix(int n);
  Matrix(const Matrix& ref);
  Matrix& operator=(const Matrix& ref);
  Matrix operator*(const Matrix& rhs) const;
  long long& operator()(const int& row, const int& column) const;
  void toIdentity();
  void toZero();
  Matrix power(int k) const;

  friend ostream& operator<<(ostream& os, const Matrix& matrix) {
    for (int i = 0; i < matrix.n; i++) {
      for (int j = 0; j < matrix.n; j++)
        os << matrix(i, j) << ' ';
      os << endl;
    }
    return os;
  }
};
//#include "function.h"
//#ifndef FUNCTION_H
//#define FUNCTION_H
//#include <iostream>
//using namespace std;
//const int mod = 1000000009;
Matrix::~Matrix(){
  for(int i=0;i<n;i++){
      delete[] matrix[i];
  }
  delete[] matrix;
}

Matrix::Matrix(int n){
  matrix=(long long**)malloc(sizeof(long long*)*n);
  for(int i=0;i<n;i++){
    matrix[i]=(long long*)malloc(sizeof(long long)*n);
  }
  this->n=n;
}

Matrix::Matrix(const Matrix& ref){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      matrix[i][j]=ref.matrix[i][j];
    }
  }
}

Matrix& Matrix::operator=(const Matrix& ref){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      matrix[i][j]=ref.matrix[i][j];
    }
  }
}

long long& Matrix::operator()(const int& row, const int& column) const{
  return this->matrix[row][column];
}

void Matrix::toIdentity(){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j)matrix[i][j]=1;
      else matrix[i][j]=0;
    }
  }
}
void Matrix::toZero() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
      matrix[i][j] = 0;
  }
}

Matrix Matrix::operator*(const Matrix& rhs) const{
  Matrix ret=Matrix(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      ret.matrix[i][j]=0;
      for(int k=0;k<n;k++){
        ret.matrix[i][j]+=matrix[i][k]*rhs.matrix[k][j]%mod;
      }
      ret.matrix[i][j]%=mod;
    }
  }
  return ret;
}

Matrix Matrix::power(int k) const{
  for(int i=0;i<n-1;i++){
    for(int j=0;j<n;j++){
      if(i+1==j)matrix[i][j]=1;
      else matrix[i][j]=0;
    }
  }
  for(int j=0;j<n;j++){
    matrix[n-1][j]=1;
  }
  Matrix init=Matrix(n);
  init.toIdentity();
  Matrix a=Matrix(n);
  a=*this;
  while(k>0){
    if(k%2==1)init=init*a;
    a=a*a;
    k/=2;
  }
  return init;
}

Matrix constructMatrix(int n){
  Matrix ret=Matrix(n);
  return ret;
}
//#endif


int main() {
  int n, m;
  cin >> n >> m;
  if (m <= n) {
    cout << 1 << endl;
  } else {
    Matrix base = constructMatrix(n);
    
    base = base.power(m - n);
    //cout<<base;
    int ans = 0;
    for (int i = 0; i < n; i++)
      ans = (ans + base(n - 1, i)) % mod;
    cout << ans << endl;
  }
  return 0;
}