#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
using namespace std;
inline void rdl(long long &val) {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void rdi(int &val) {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline long long rdl() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline int rdi() {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void _write(int x) {
  write(x);
  putchar(' ');
}
inline void print(int x) {
  write(x);
  putchar('\n');
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void _write(long long x) {
  write(x);
  putchar(' ');
}
inline void print(long long x) {
  write(x);
  putchar('\n');
}
struct dsu {
  int par[200200];
  inline void init(int _n) {
    for (int i = 0; i < _n; ++i) par[i] = i;
  }
  inline int find(int now) {
    if (par[now] == now) return now;
    return par[now] = find(par[now]);
  }
  inline bool uni(int a, int b) {
    int Pa(find(a)), Pb(find(b));
    if (Pa == Pb) return false;
    par[Pa] = Pb;
    return true;
  }
};
const int md = 1000000009;
inline void add(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
int dp[1001][33][33][33][2], n, h;
int a[1001][33];
inline void prepare() {
  a[800][20] = 539577677;
  a[801][20] = 0;
  a[802][20] = 0;
  a[803][20] = 0;
  a[804][20] = 0;
  a[805][20] = 0;
  a[806][20] = 0;
  a[807][20] = 0;
  a[808][20] = 0;
  a[809][20] = 0;
  a[810][20] = 0;
  a[811][20] = 0;
  a[812][20] = 0;
  a[813][20] = 0;
  a[814][20] = 0;
  a[815][20] = 0;
  a[816][20] = 0;
  a[817][20] = 0;
  a[818][20] = 0;
  a[819][20] = 0;
  a[820][20] = 0;
  a[821][20] = 0;
  a[822][20] = 0;
  a[823][20] = 0;
  a[824][20] = 0;
  a[825][20] = 0;
  a[826][20] = 0;
  a[827][20] = 0;
  a[828][20] = 0;
  a[829][20] = 0;
  a[830][20] = 0;
  a[831][20] = 0;
  a[832][20] = 0;
  a[833][20] = 0;
  a[834][20] = 0;
  a[835][20] = 0;
  a[836][20] = 0;
  a[837][20] = 0;
  a[838][20] = 0;
  a[839][20] = 0;
  a[840][20] = 0;
  a[841][20] = 0;
  a[842][20] = 0;
  a[843][20] = 0;
  a[844][20] = 0;
  a[845][20] = 0;
  a[846][20] = 0;
  a[847][20] = 0;
  a[848][20] = 0;
  a[849][20] = 0;
  a[850][20] = 0;
  a[851][20] = 0;
  a[852][20] = 0;
  a[853][20] = 0;
  a[854][20] = 0;
  a[855][20] = 0;
  a[856][20] = 0;
  a[857][20] = 0;
  a[858][20] = 0;
  a[859][20] = 0;
  a[860][20] = 0;
  a[861][20] = 0;
  a[862][20] = 0;
  a[863][20] = 0;
  a[864][20] = 0;
  a[865][20] = 0;
  a[866][20] = 0;
  a[867][20] = 0;
  a[868][20] = 0;
  a[869][20] = 0;
  a[870][20] = 0;
  a[871][20] = 0;
  a[872][20] = 0;
  a[873][20] = 0;
  a[874][20] = 0;
  a[875][20] = 0;
  a[876][20] = 0;
  a[877][20] = 0;
  a[878][20] = 0;
  a[879][20] = 0;
  a[880][20] = 0;
  a[881][20] = 0;
  a[882][20] = 0;
  a[883][20] = 0;
  a[884][20] = 0;
  a[885][20] = 0;
  a[886][20] = 0;
  a[887][20] = 0;
  a[888][20] = 0;
  a[889][20] = 0;
  a[890][20] = 0;
  a[891][20] = 0;
  a[892][20] = 0;
  a[893][20] = 0;
  a[894][20] = 0;
  a[895][20] = 0;
  a[896][20] = 0;
  a[897][20] = 0;
  a[898][20] = 0;
  a[899][20] = 0;
  a[900][20] = 0;
  a[901][20] = 0;
  a[902][20] = 0;
  a[903][20] = 0;
  a[904][20] = 0;
  a[905][20] = 0;
  a[906][20] = 0;
  a[907][20] = 0;
  a[908][20] = 0;
  a[909][20] = 0;
  a[910][20] = 0;
  a[911][20] = 0;
  a[912][20] = 0;
  a[913][20] = 0;
  a[914][20] = 0;
  a[915][20] = 0;
  a[916][20] = 0;
  a[917][20] = 0;
  a[918][20] = 0;
  a[919][20] = 0;
  a[920][20] = 0;
  a[921][20] = 0;
  a[922][20] = 0;
  a[923][20] = 0;
  a[924][20] = 0;
  a[925][20] = 0;
  a[926][20] = 0;
  a[927][20] = 0;
  a[928][20] = 0;
  a[929][20] = 0;
  a[930][20] = 0;
  a[931][20] = 0;
  a[932][20] = 0;
  a[933][20] = 0;
  a[934][20] = 0;
  a[935][20] = 0;
  a[936][20] = 0;
  a[937][20] = 0;
  a[938][20] = 0;
  a[939][20] = 0;
  a[940][20] = 0;
  a[941][20] = 0;
  a[942][20] = 0;
  a[943][20] = 0;
  a[944][20] = 0;
  a[945][20] = 0;
  a[946][20] = 0;
  a[947][20] = 0;
  a[948][20] = 0;
  a[949][20] = 0;
  a[950][20] = 0;
  a[951][20] = 0;
  a[952][20] = 0;
  a[953][20] = 0;
  a[954][20] = 0;
  a[955][20] = 0;
  a[956][20] = 0;
  a[957][20] = 0;
  a[958][20] = 0;
  a[959][20] = 0;
  a[960][20] = 0;
  a[961][20] = 0;
  a[962][20] = 0;
  a[963][20] = 0;
  a[964][20] = 0;
  a[965][20] = 0;
  a[966][20] = 0;
  a[967][20] = 0;
  a[968][20] = 0;
  a[969][20] = 0;
  a[970][20] = 0;
  a[971][20] = 0;
  a[972][20] = 0;
  a[973][20] = 0;
  a[974][20] = 0;
  a[975][20] = 0;
  a[976][20] = 0;
  a[977][20] = 0;
  a[978][20] = 0;
  a[979][20] = 0;
  a[980][20] = 0;
  a[981][20] = 0;
  a[982][20] = 0;
  a[983][20] = 0;
  a[984][20] = 0;
  a[985][20] = 0;
  a[986][20] = 0;
  a[987][20] = 0;
  a[988][20] = 0;
  a[989][20] = 0;
  a[990][20] = 0;
  a[991][20] = 0;
  a[992][20] = 0;
  a[993][20] = 0;
  a[994][20] = 0;
  a[995][20] = 0;
  a[996][20] = 0;
  a[997][20] = 0;
  a[998][20] = 0;
  a[999][20] = 0;
  a[1000][20] = 0;
  a[800][21] = 419889129;
  a[801][21] = 0;
  a[802][21] = 0;
  a[803][21] = 0;
  a[804][21] = 0;
  a[805][21] = 0;
  a[806][21] = 0;
  a[807][21] = 0;
  a[808][21] = 0;
  a[809][21] = 0;
  a[810][21] = 0;
  a[811][21] = 0;
  a[812][21] = 0;
  a[813][21] = 0;
  a[814][21] = 0;
  a[815][21] = 0;
  a[816][21] = 0;
  a[817][21] = 0;
  a[818][21] = 0;
  a[819][21] = 0;
  a[820][21] = 0;
  a[821][21] = 0;
  a[822][21] = 0;
  a[823][21] = 0;
  a[824][21] = 0;
  a[825][21] = 0;
  a[826][21] = 0;
  a[827][21] = 0;
  a[828][21] = 0;
  a[829][21] = 0;
  a[830][21] = 0;
  a[831][21] = 0;
  a[832][21] = 0;
  a[833][21] = 0;
  a[834][21] = 0;
  a[835][21] = 0;
  a[836][21] = 0;
  a[837][21] = 0;
  a[838][21] = 0;
  a[839][21] = 0;
  a[840][21] = 0;
  a[841][21] = 0;
  a[842][21] = 0;
  a[843][21] = 0;
  a[844][21] = 0;
  a[845][21] = 0;
  a[846][21] = 0;
  a[847][21] = 0;
  a[848][21] = 0;
  a[849][21] = 0;
  a[850][21] = 0;
  a[851][21] = 0;
  a[852][21] = 0;
  a[853][21] = 0;
  a[854][21] = 0;
  a[855][21] = 0;
  a[856][21] = 0;
  a[857][21] = 0;
  a[858][21] = 0;
  a[859][21] = 0;
  a[860][21] = 0;
  a[861][21] = 0;
  a[862][21] = 0;
  a[863][21] = 0;
  a[864][21] = 0;
  a[865][21] = 0;
  a[866][21] = 0;
  a[867][21] = 0;
  a[868][21] = 0;
  a[869][21] = 0;
  a[870][21] = 0;
  a[871][21] = 0;
  a[872][21] = 0;
  a[873][21] = 0;
  a[874][21] = 0;
  a[875][21] = 0;
  a[876][21] = 0;
  a[877][21] = 0;
  a[878][21] = 0;
  a[879][21] = 0;
  a[880][21] = 0;
  a[881][21] = 0;
  a[882][21] = 0;
  a[883][21] = 0;
  a[884][21] = 0;
  a[885][21] = 0;
  a[886][21] = 0;
  a[887][21] = 0;
  a[888][21] = 0;
  a[889][21] = 0;
  a[890][21] = 0;
  a[891][21] = 0;
  a[892][21] = 0;
  a[893][21] = 0;
  a[894][21] = 0;
  a[895][21] = 0;
  a[896][21] = 0;
  a[897][21] = 0;
  a[898][21] = 0;
  a[899][21] = 0;
  a[900][21] = 0;
  a[901][21] = 0;
  a[902][21] = 0;
  a[903][21] = 0;
  a[904][21] = 0;
  a[905][21] = 0;
  a[906][21] = 0;
  a[907][21] = 0;
  a[908][21] = 0;
  a[909][21] = 0;
  a[910][21] = 0;
  a[911][21] = 0;
  a[912][21] = 0;
  a[913][21] = 0;
  a[914][21] = 0;
  a[915][21] = 0;
  a[916][21] = 0;
  a[917][21] = 0;
  a[918][21] = 0;
  a[919][21] = 0;
  a[920][21] = 0;
  a[921][21] = 0;
  a[922][21] = 0;
  a[923][21] = 0;
  a[924][21] = 0;
  a[925][21] = 0;
  a[926][21] = 0;
  a[927][21] = 0;
  a[928][21] = 0;
  a[929][21] = 0;
  a[930][21] = 0;
  a[931][21] = 0;
  a[932][21] = 0;
  a[933][21] = 0;
  a[934][21] = 0;
  a[935][21] = 0;
  a[936][21] = 0;
  a[937][21] = 0;
  a[938][21] = 0;
  a[939][21] = 0;
  a[940][21] = 0;
  a[941][21] = 0;
  a[942][21] = 0;
  a[943][21] = 0;
  a[944][21] = 0;
  a[945][21] = 0;
  a[946][21] = 0;
  a[947][21] = 0;
  a[948][21] = 0;
  a[949][21] = 0;
  a[950][21] = 0;
  a[951][21] = 0;
  a[952][21] = 0;
  a[953][21] = 0;
  a[954][21] = 0;
  a[955][21] = 0;
  a[956][21] = 0;
  a[957][21] = 0;
  a[958][21] = 0;
  a[959][21] = 0;
  a[960][21] = 0;
  a[961][21] = 0;
  a[962][21] = 0;
  a[963][21] = 0;
  a[964][21] = 0;
  a[965][21] = 0;
  a[966][21] = 0;
  a[967][21] = 0;
  a[968][21] = 0;
  a[969][21] = 0;
  a[970][21] = 0;
  a[971][21] = 0;
  a[972][21] = 0;
  a[973][21] = 0;
  a[974][21] = 0;
  a[975][21] = 0;
  a[976][21] = 0;
  a[977][21] = 0;
  a[978][21] = 0;
  a[979][21] = 0;
  a[980][21] = 0;
  a[981][21] = 0;
  a[982][21] = 0;
  a[983][21] = 0;
  a[984][21] = 0;
  a[985][21] = 0;
  a[986][21] = 0;
  a[987][21] = 0;
  a[988][21] = 0;
  a[989][21] = 0;
  a[990][21] = 0;
  a[991][21] = 0;
  a[992][21] = 0;
  a[993][21] = 0;
  a[994][21] = 0;
  a[995][21] = 0;
  a[996][21] = 0;
  a[997][21] = 0;
  a[998][21] = 0;
  a[999][21] = 0;
  a[1000][21] = 0;
  a[800][22] = 322148007;
  a[801][22] = 0;
  a[802][22] = 0;
  a[803][22] = 0;
  a[804][22] = 0;
  a[805][22] = 0;
  a[806][22] = 0;
  a[807][22] = 0;
  a[808][22] = 0;
  a[809][22] = 0;
  a[810][22] = 0;
  a[811][22] = 0;
  a[812][22] = 0;
  a[813][22] = 0;
  a[814][22] = 0;
  a[815][22] = 0;
  a[816][22] = 0;
  a[817][22] = 0;
  a[818][22] = 0;
  a[819][22] = 0;
  a[820][22] = 0;
  a[821][22] = 0;
  a[822][22] = 0;
  a[823][22] = 0;
  a[824][22] = 0;
  a[825][22] = 0;
  a[826][22] = 0;
  a[827][22] = 0;
  a[828][22] = 0;
  a[829][22] = 0;
  a[830][22] = 0;
  a[831][22] = 0;
  a[832][22] = 0;
  a[833][22] = 0;
  a[834][22] = 0;
  a[835][22] = 0;
  a[836][22] = 0;
  a[837][22] = 0;
  a[838][22] = 0;
  a[839][22] = 0;
  a[840][22] = 0;
  a[841][22] = 0;
  a[842][22] = 0;
  a[843][22] = 0;
  a[844][22] = 0;
  a[845][22] = 0;
  a[846][22] = 0;
  a[847][22] = 0;
  a[848][22] = 0;
  a[849][22] = 0;
  a[850][22] = 0;
  a[851][22] = 0;
  a[852][22] = 0;
  a[853][22] = 0;
  a[854][22] = 0;
  a[855][22] = 0;
  a[856][22] = 0;
  a[857][22] = 0;
  a[858][22] = 0;
  a[859][22] = 0;
  a[860][22] = 0;
  a[861][22] = 0;
  a[862][22] = 0;
  a[863][22] = 0;
  a[864][22] = 0;
  a[865][22] = 0;
  a[866][22] = 0;
  a[867][22] = 0;
  a[868][22] = 0;
  a[869][22] = 0;
  a[870][22] = 0;
  a[871][22] = 0;
  a[872][22] = 0;
  a[873][22] = 0;
  a[874][22] = 0;
  a[875][22] = 0;
  a[876][22] = 0;
  a[877][22] = 0;
  a[878][22] = 0;
  a[879][22] = 0;
  a[880][22] = 0;
  a[881][22] = 0;
  a[882][22] = 0;
  a[883][22] = 0;
  a[884][22] = 0;
  a[885][22] = 0;
  a[886][22] = 0;
  a[887][22] = 0;
  a[888][22] = 0;
  a[889][22] = 0;
  a[890][22] = 0;
  a[891][22] = 0;
  a[892][22] = 0;
  a[893][22] = 0;
  a[894][22] = 0;
  a[895][22] = 0;
  a[896][22] = 0;
  a[897][22] = 0;
  a[898][22] = 0;
  a[899][22] = 0;
  a[900][22] = 0;
  a[901][22] = 0;
  a[902][22] = 0;
  a[903][22] = 0;
  a[904][22] = 0;
  a[905][22] = 0;
  a[906][22] = 0;
  a[907][22] = 0;
  a[908][22] = 0;
  a[909][22] = 0;
  a[910][22] = 0;
  a[911][22] = 0;
  a[912][22] = 0;
  a[913][22] = 0;
  a[914][22] = 0;
  a[915][22] = 0;
  a[916][22] = 0;
  a[917][22] = 0;
  a[918][22] = 0;
  a[919][22] = 0;
  a[920][22] = 0;
  a[921][22] = 0;
  a[922][22] = 0;
  a[923][22] = 0;
  a[924][22] = 0;
  a[925][22] = 0;
  a[926][22] = 0;
  a[927][22] = 0;
  a[928][22] = 0;
  a[929][22] = 0;
  a[930][22] = 0;
  a[931][22] = 0;
  a[932][22] = 0;
  a[933][22] = 0;
  a[934][22] = 0;
  a[935][22] = 0;
  a[936][22] = 0;
  a[937][22] = 0;
  a[938][22] = 0;
  a[939][22] = 0;
  a[940][22] = 0;
  a[941][22] = 0;
  a[942][22] = 0;
  a[943][22] = 0;
  a[944][22] = 0;
  a[945][22] = 0;
  a[946][22] = 0;
  a[947][22] = 0;
  a[948][22] = 0;
  a[949][22] = 0;
  a[950][22] = 0;
  a[951][22] = 0;
  a[952][22] = 0;
  a[953][22] = 0;
  a[954][22] = 0;
  a[955][22] = 0;
  a[956][22] = 0;
  a[957][22] = 0;
  a[958][22] = 0;
  a[959][22] = 0;
  a[960][22] = 0;
  a[961][22] = 0;
  a[962][22] = 0;
  a[963][22] = 0;
  a[964][22] = 0;
  a[965][22] = 0;
  a[966][22] = 0;
  a[967][22] = 0;
  a[968][22] = 0;
  a[969][22] = 0;
  a[970][22] = 0;
  a[971][22] = 0;
  a[972][22] = 0;
  a[973][22] = 0;
  a[974][22] = 0;
  a[975][22] = 0;
  a[976][22] = 0;
  a[977][22] = 0;
  a[978][22] = 0;
  a[979][22] = 0;
  a[980][22] = 0;
  a[981][22] = 0;
  a[982][22] = 0;
  a[983][22] = 0;
  a[984][22] = 0;
  a[985][22] = 0;
  a[986][22] = 0;
  a[987][22] = 0;
  a[988][22] = 0;
  a[989][22] = 0;
  a[990][22] = 0;
  a[991][22] = 0;
  a[992][22] = 0;
  a[993][22] = 0;
  a[994][22] = 0;
  a[995][22] = 0;
  a[996][22] = 0;
  a[997][22] = 0;
  a[998][22] = 0;
  a[999][22] = 0;
  a[1000][22] = 0;
  a[800][23] = 967760392;
  a[801][23] = 0;
  a[802][23] = 0;
  a[803][23] = 0;
  a[804][23] = 0;
  a[805][23] = 0;
  a[806][23] = 0;
  a[807][23] = 0;
  a[808][23] = 0;
  a[809][23] = 0;
  a[810][23] = 0;
  a[811][23] = 0;
  a[812][23] = 0;
  a[813][23] = 0;
  a[814][23] = 0;
  a[815][23] = 0;
  a[816][23] = 0;
  a[817][23] = 0;
  a[818][23] = 0;
  a[819][23] = 0;
  a[820][23] = 0;
  a[821][23] = 0;
  a[822][23] = 0;
  a[823][23] = 0;
  a[824][23] = 0;
  a[825][23] = 0;
  a[826][23] = 0;
  a[827][23] = 0;
  a[828][23] = 0;
  a[829][23] = 0;
  a[830][23] = 0;
  a[831][23] = 0;
  a[832][23] = 0;
  a[833][23] = 0;
  a[834][23] = 0;
  a[835][23] = 0;
  a[836][23] = 0;
  a[837][23] = 0;
  a[838][23] = 0;
  a[839][23] = 0;
  a[840][23] = 0;
  a[841][23] = 0;
  a[842][23] = 0;
  a[843][23] = 0;
  a[844][23] = 0;
  a[845][23] = 0;
  a[846][23] = 0;
  a[847][23] = 0;
  a[848][23] = 0;
  a[849][23] = 0;
  a[850][23] = 0;
  a[851][23] = 0;
  a[852][23] = 0;
  a[853][23] = 0;
  a[854][23] = 0;
  a[855][23] = 0;
  a[856][23] = 0;
  a[857][23] = 0;
  a[858][23] = 0;
  a[859][23] = 0;
  a[860][23] = 0;
  a[861][23] = 0;
  a[862][23] = 0;
  a[863][23] = 0;
  a[864][23] = 0;
  a[865][23] = 0;
  a[866][23] = 0;
  a[867][23] = 0;
  a[868][23] = 0;
  a[869][23] = 0;
  a[870][23] = 0;
  a[871][23] = 0;
  a[872][23] = 0;
  a[873][23] = 0;
  a[874][23] = 0;
  a[875][23] = 0;
  a[876][23] = 0;
  a[877][23] = 0;
  a[878][23] = 0;
  a[879][23] = 0;
  a[880][23] = 0;
  a[881][23] = 0;
  a[882][23] = 0;
  a[883][23] = 0;
  a[884][23] = 0;
  a[885][23] = 0;
  a[886][23] = 0;
  a[887][23] = 0;
  a[888][23] = 0;
  a[889][23] = 0;
  a[890][23] = 0;
  a[891][23] = 0;
  a[892][23] = 0;
  a[893][23] = 0;
  a[894][23] = 0;
  a[895][23] = 0;
  a[896][23] = 0;
  a[897][23] = 0;
  a[898][23] = 0;
  a[899][23] = 0;
  a[900][23] = 0;
  a[901][23] = 0;
  a[902][23] = 0;
  a[903][23] = 0;
  a[904][23] = 0;
  a[905][23] = 0;
  a[906][23] = 0;
  a[907][23] = 0;
  a[908][23] = 0;
  a[909][23] = 0;
  a[910][23] = 0;
  a[911][23] = 0;
  a[912][23] = 0;
  a[913][23] = 0;
  a[914][23] = 0;
  a[915][23] = 0;
  a[916][23] = 0;
  a[917][23] = 0;
  a[918][23] = 0;
  a[919][23] = 0;
  a[920][23] = 0;
  a[921][23] = 0;
  a[922][23] = 0;
  a[923][23] = 0;
  a[924][23] = 0;
  a[925][23] = 0;
  a[926][23] = 0;
  a[927][23] = 0;
  a[928][23] = 0;
  a[929][23] = 0;
  a[930][23] = 0;
  a[931][23] = 0;
  a[932][23] = 0;
  a[933][23] = 0;
  a[934][23] = 0;
  a[935][23] = 0;
  a[936][23] = 0;
  a[937][23] = 0;
  a[938][23] = 0;
  a[939][23] = 0;
  a[940][23] = 0;
  a[941][23] = 0;
  a[942][23] = 0;
  a[943][23] = 0;
  a[944][23] = 0;
  a[945][23] = 0;
  a[946][23] = 0;
  a[947][23] = 0;
  a[948][23] = 0;
  a[949][23] = 0;
  a[950][23] = 0;
  a[951][23] = 0;
  a[952][23] = 0;
  a[953][23] = 0;
  a[954][23] = 0;
  a[955][23] = 0;
  a[956][23] = 0;
  a[957][23] = 0;
  a[958][23] = 0;
  a[959][23] = 0;
  a[960][23] = 0;
  a[961][23] = 0;
  a[962][23] = 0;
  a[963][23] = 0;
  a[964][23] = 0;
  a[965][23] = 0;
  a[966][23] = 0;
  a[967][23] = 0;
  a[968][23] = 0;
  a[969][23] = 0;
  a[970][23] = 0;
  a[971][23] = 0;
  a[972][23] = 0;
  a[973][23] = 0;
  a[974][23] = 0;
  a[975][23] = 0;
  a[976][23] = 0;
  a[977][23] = 0;
  a[978][23] = 0;
  a[979][23] = 0;
  a[980][23] = 0;
  a[981][23] = 0;
  a[982][23] = 0;
  a[983][23] = 0;
  a[984][23] = 0;
  a[985][23] = 0;
  a[986][23] = 0;
  a[987][23] = 0;
  a[988][23] = 0;
  a[989][23] = 0;
  a[990][23] = 0;
  a[991][23] = 0;
  a[992][23] = 0;
  a[993][23] = 0;
  a[994][23] = 0;
  a[995][23] = 0;
  a[996][23] = 0;
  a[997][23] = 0;
  a[998][23] = 0;
  a[999][23] = 0;
  a[1000][23] = 0;
  a[800][24] = 863522038;
  a[801][24] = 0;
  a[802][24] = 0;
  a[803][24] = 0;
  a[804][24] = 0;
  a[805][24] = 0;
  a[806][24] = 0;
  a[807][24] = 0;
  a[808][24] = 0;
  a[809][24] = 0;
  a[810][24] = 0;
  a[811][24] = 0;
  a[812][24] = 0;
  a[813][24] = 0;
  a[814][24] = 0;
  a[815][24] = 0;
  a[816][24] = 0;
  a[817][24] = 0;
  a[818][24] = 0;
  a[819][24] = 0;
  a[820][24] = 0;
  a[821][24] = 0;
  a[822][24] = 0;
  a[823][24] = 0;
  a[824][24] = 0;
  a[825][24] = 0;
  a[826][24] = 0;
  a[827][24] = 0;
  a[828][24] = 0;
  a[829][24] = 0;
  a[830][24] = 0;
  a[831][24] = 0;
  a[832][24] = 0;
  a[833][24] = 0;
  a[834][24] = 0;
  a[835][24] = 0;
  a[836][24] = 0;
  a[837][24] = 0;
  a[838][24] = 0;
  a[839][24] = 0;
  a[840][24] = 0;
  a[841][24] = 0;
  a[842][24] = 0;
  a[843][24] = 0;
  a[844][24] = 0;
  a[845][24] = 0;
  a[846][24] = 0;
  a[847][24] = 0;
  a[848][24] = 0;
  a[849][24] = 0;
  a[850][24] = 0;
  a[851][24] = 0;
  a[852][24] = 0;
  a[853][24] = 0;
  a[854][24] = 0;
  a[855][24] = 0;
  a[856][24] = 0;
  a[857][24] = 0;
  a[858][24] = 0;
  a[859][24] = 0;
  a[860][24] = 0;
  a[861][24] = 0;
  a[862][24] = 0;
  a[863][24] = 0;
  a[864][24] = 0;
  a[865][24] = 0;
  a[866][24] = 0;
  a[867][24] = 0;
  a[868][24] = 0;
  a[869][24] = 0;
  a[870][24] = 0;
  a[871][24] = 0;
  a[872][24] = 0;
  a[873][24] = 0;
  a[874][24] = 0;
  a[875][24] = 0;
  a[876][24] = 0;
  a[877][24] = 0;
  a[878][24] = 0;
  a[879][24] = 0;
  a[880][24] = 0;
  a[881][24] = 0;
  a[882][24] = 0;
  a[883][24] = 0;
  a[884][24] = 0;
  a[885][24] = 0;
  a[886][24] = 0;
  a[887][24] = 0;
  a[888][24] = 0;
  a[889][24] = 0;
  a[890][24] = 0;
  a[891][24] = 0;
  a[892][24] = 0;
  a[893][24] = 0;
  a[894][24] = 0;
  a[895][24] = 0;
  a[896][24] = 0;
  a[897][24] = 0;
  a[898][24] = 0;
  a[899][24] = 0;
  a[900][24] = 0;
  a[901][24] = 0;
  a[902][24] = 0;
  a[903][24] = 0;
  a[904][24] = 0;
  a[905][24] = 0;
  a[906][24] = 0;
  a[907][24] = 0;
  a[908][24] = 0;
  a[909][24] = 0;
  a[910][24] = 0;
  a[911][24] = 0;
  a[912][24] = 0;
  a[913][24] = 0;
  a[914][24] = 0;
  a[915][24] = 0;
  a[916][24] = 0;
  a[917][24] = 0;
  a[918][24] = 0;
  a[919][24] = 0;
  a[920][24] = 0;
  a[921][24] = 0;
  a[922][24] = 0;
  a[923][24] = 0;
  a[924][24] = 0;
  a[925][24] = 0;
  a[926][24] = 0;
  a[927][24] = 0;
  a[928][24] = 0;
  a[929][24] = 0;
  a[930][24] = 0;
  a[931][24] = 0;
  a[932][24] = 0;
  a[933][24] = 0;
  a[934][24] = 0;
  a[935][24] = 0;
  a[936][24] = 0;
  a[937][24] = 0;
  a[938][24] = 0;
  a[939][24] = 0;
  a[940][24] = 0;
  a[941][24] = 0;
  a[942][24] = 0;
  a[943][24] = 0;
  a[944][24] = 0;
  a[945][24] = 0;
  a[946][24] = 0;
  a[947][24] = 0;
  a[948][24] = 0;
  a[949][24] = 0;
  a[950][24] = 0;
  a[951][24] = 0;
  a[952][24] = 0;
  a[953][24] = 0;
  a[954][24] = 0;
  a[955][24] = 0;
  a[956][24] = 0;
  a[957][24] = 0;
  a[958][24] = 0;
  a[959][24] = 0;
  a[960][24] = 0;
  a[961][24] = 0;
  a[962][24] = 0;
  a[963][24] = 0;
  a[964][24] = 0;
  a[965][24] = 0;
  a[966][24] = 0;
  a[967][24] = 0;
  a[968][24] = 0;
  a[969][24] = 0;
  a[970][24] = 0;
  a[971][24] = 0;
  a[972][24] = 0;
  a[973][24] = 0;
  a[974][24] = 0;
  a[975][24] = 0;
  a[976][24] = 0;
  a[977][24] = 0;
  a[978][24] = 0;
  a[979][24] = 0;
  a[980][24] = 0;
  a[981][24] = 0;
  a[982][24] = 0;
  a[983][24] = 0;
  a[984][24] = 0;
  a[985][24] = 0;
  a[986][24] = 0;
  a[987][24] = 0;
  a[988][24] = 0;
  a[989][24] = 0;
  a[990][24] = 0;
  a[991][24] = 0;
  a[992][24] = 0;
  a[993][24] = 0;
  a[994][24] = 0;
  a[995][24] = 0;
  a[996][24] = 0;
  a[997][24] = 0;
  a[998][24] = 0;
  a[999][24] = 0;
  a[1000][24] = 0;
  a[800][25] = 223364203;
  a[801][25] = 0;
  a[802][25] = 0;
  a[803][25] = 0;
  a[804][25] = 0;
  a[805][25] = 0;
  a[806][25] = 0;
  a[807][25] = 0;
  a[808][25] = 0;
  a[809][25] = 0;
  a[810][25] = 0;
  a[811][25] = 0;
  a[812][25] = 0;
  a[813][25] = 0;
  a[814][25] = 0;
  a[815][25] = 0;
  a[816][25] = 0;
  a[817][25] = 0;
  a[818][25] = 0;
  a[819][25] = 0;
  a[820][25] = 0;
  a[821][25] = 0;
  a[822][25] = 0;
  a[823][25] = 0;
  a[824][25] = 0;
  a[825][25] = 0;
  a[826][25] = 0;
  a[827][25] = 0;
  a[828][25] = 0;
  a[829][25] = 0;
  a[830][25] = 0;
  a[831][25] = 0;
  a[832][25] = 0;
  a[833][25] = 0;
  a[834][25] = 0;
  a[835][25] = 0;
  a[836][25] = 0;
  a[837][25] = 0;
  a[838][25] = 0;
  a[839][25] = 0;
  a[840][25] = 0;
  a[841][25] = 0;
  a[842][25] = 0;
  a[843][25] = 0;
  a[844][25] = 0;
  a[845][25] = 0;
  a[846][25] = 0;
  a[847][25] = 0;
  a[848][25] = 0;
  a[849][25] = 0;
  a[850][25] = 0;
  a[851][25] = 0;
  a[852][25] = 0;
  a[853][25] = 0;
  a[854][25] = 0;
  a[855][25] = 0;
  a[856][25] = 0;
  a[857][25] = 0;
  a[858][25] = 0;
  a[859][25] = 0;
  a[860][25] = 0;
  a[861][25] = 0;
  a[862][25] = 0;
  a[863][25] = 0;
  a[864][25] = 0;
  a[865][25] = 0;
  a[866][25] = 0;
  a[867][25] = 0;
  a[868][25] = 0;
  a[869][25] = 0;
  a[870][25] = 0;
  a[871][25] = 0;
  a[872][25] = 0;
  a[873][25] = 0;
  a[874][25] = 0;
  a[875][25] = 0;
  a[876][25] = 0;
  a[877][25] = 0;
  a[878][25] = 0;
  a[879][25] = 0;
  a[880][25] = 0;
  a[881][25] = 0;
  a[882][25] = 0;
  a[883][25] = 0;
  a[884][25] = 0;
  a[885][25] = 0;
  a[886][25] = 0;
  a[887][25] = 0;
  a[888][25] = 0;
  a[889][25] = 0;
  a[890][25] = 0;
  a[891][25] = 0;
  a[892][25] = 0;
  a[893][25] = 0;
  a[894][25] = 0;
  a[895][25] = 0;
  a[896][25] = 0;
  a[897][25] = 0;
  a[898][25] = 0;
  a[899][25] = 0;
  a[900][25] = 0;
  a[901][25] = 0;
  a[902][25] = 0;
  a[903][25] = 0;
  a[904][25] = 0;
  a[905][25] = 0;
  a[906][25] = 0;
  a[907][25] = 0;
  a[908][25] = 0;
  a[909][25] = 0;
  a[910][25] = 0;
  a[911][25] = 0;
  a[912][25] = 0;
  a[913][25] = 0;
  a[914][25] = 0;
  a[915][25] = 0;
  a[916][25] = 0;
  a[917][25] = 0;
  a[918][25] = 0;
  a[919][25] = 0;
  a[920][25] = 0;
  a[921][25] = 0;
  a[922][25] = 0;
  a[923][25] = 0;
  a[924][25] = 0;
  a[925][25] = 0;
  a[926][25] = 0;
  a[927][25] = 0;
  a[928][25] = 0;
  a[929][25] = 0;
  a[930][25] = 0;
  a[931][25] = 0;
  a[932][25] = 0;
  a[933][25] = 0;
  a[934][25] = 0;
  a[935][25] = 0;
  a[936][25] = 0;
  a[937][25] = 0;
  a[938][25] = 0;
  a[939][25] = 0;
  a[940][25] = 0;
  a[941][25] = 0;
  a[942][25] = 0;
  a[943][25] = 0;
  a[944][25] = 0;
  a[945][25] = 0;
  a[946][25] = 0;
  a[947][25] = 0;
  a[948][25] = 0;
  a[949][25] = 0;
  a[950][25] = 0;
  a[951][25] = 0;
  a[952][25] = 0;
  a[953][25] = 0;
  a[954][25] = 0;
  a[955][25] = 0;
  a[956][25] = 0;
  a[957][25] = 0;
  a[958][25] = 0;
  a[959][25] = 0;
  a[960][25] = 0;
  a[961][25] = 0;
  a[962][25] = 0;
  a[963][25] = 0;
  a[964][25] = 0;
  a[965][25] = 0;
  a[966][25] = 0;
  a[967][25] = 0;
  a[968][25] = 0;
  a[969][25] = 0;
  a[970][25] = 0;
  a[971][25] = 0;
  a[972][25] = 0;
  a[973][25] = 0;
  a[974][25] = 0;
  a[975][25] = 0;
  a[976][25] = 0;
  a[977][25] = 0;
  a[978][25] = 0;
  a[979][25] = 0;
  a[980][25] = 0;
  a[981][25] = 0;
  a[982][25] = 0;
  a[983][25] = 0;
  a[984][25] = 0;
  a[985][25] = 0;
  a[986][25] = 0;
  a[987][25] = 0;
  a[988][25] = 0;
  a[989][25] = 0;
  a[990][25] = 0;
  a[991][25] = 0;
  a[992][25] = 0;
  a[993][25] = 0;
  a[994][25] = 0;
  a[995][25] = 0;
  a[996][25] = 0;
  a[997][25] = 0;
  a[998][25] = 0;
  a[999][25] = 0;
  a[1000][25] = 0;
  a[800][26] = 135169406;
  a[801][26] = 0;
  a[802][26] = 0;
  a[803][26] = 0;
  a[804][26] = 0;
  a[805][26] = 0;
  a[806][26] = 0;
  a[807][26] = 0;
  a[808][26] = 0;
  a[809][26] = 0;
  a[810][26] = 0;
  a[811][26] = 0;
  a[812][26] = 0;
  a[813][26] = 0;
  a[814][26] = 0;
  a[815][26] = 0;
  a[816][26] = 0;
  a[817][26] = 0;
  a[818][26] = 0;
  a[819][26] = 0;
  a[820][26] = 0;
  a[821][26] = 0;
  a[822][26] = 0;
  a[823][26] = 0;
  a[824][26] = 0;
  a[825][26] = 0;
  a[826][26] = 0;
  a[827][26] = 0;
  a[828][26] = 0;
  a[829][26] = 0;
  a[830][26] = 0;
  a[831][26] = 0;
  a[832][26] = 0;
  a[833][26] = 0;
  a[834][26] = 0;
  a[835][26] = 0;
  a[836][26] = 0;
  a[837][26] = 0;
  a[838][26] = 0;
  a[839][26] = 0;
  a[840][26] = 0;
  a[841][26] = 0;
  a[842][26] = 0;
  a[843][26] = 0;
  a[844][26] = 0;
  a[845][26] = 0;
  a[846][26] = 0;
  a[847][26] = 0;
  a[848][26] = 0;
  a[849][26] = 0;
  a[850][26] = 0;
  a[851][26] = 0;
  a[852][26] = 0;
  a[853][26] = 0;
  a[854][26] = 0;
  a[855][26] = 0;
  a[856][26] = 0;
  a[857][26] = 0;
  a[858][26] = 0;
  a[859][26] = 0;
  a[860][26] = 0;
  a[861][26] = 0;
  a[862][26] = 0;
  a[863][26] = 0;
  a[864][26] = 0;
  a[865][26] = 0;
  a[866][26] = 0;
  a[867][26] = 0;
  a[868][26] = 0;
  a[869][26] = 0;
  a[870][26] = 0;
  a[871][26] = 0;
  a[872][26] = 0;
  a[873][26] = 0;
  a[874][26] = 0;
  a[875][26] = 0;
  a[876][26] = 0;
  a[877][26] = 0;
  a[878][26] = 0;
  a[879][26] = 0;
  a[880][26] = 0;
  a[881][26] = 0;
  a[882][26] = 0;
  a[883][26] = 0;
  a[884][26] = 0;
  a[885][26] = 0;
  a[886][26] = 0;
  a[887][26] = 0;
  a[888][26] = 0;
  a[889][26] = 0;
  a[890][26] = 0;
  a[891][26] = 0;
  a[892][26] = 0;
  a[893][26] = 0;
  a[894][26] = 0;
  a[895][26] = 0;
  a[896][26] = 0;
  a[897][26] = 0;
  a[898][26] = 0;
  a[899][26] = 0;
  a[900][26] = 0;
  a[901][26] = 0;
  a[902][26] = 0;
  a[903][26] = 0;
  a[904][26] = 0;
  a[905][26] = 0;
  a[906][26] = 0;
  a[907][26] = 0;
  a[908][26] = 0;
  a[909][26] = 0;
  a[910][26] = 0;
  a[911][26] = 0;
  a[912][26] = 0;
  a[913][26] = 0;
  a[914][26] = 0;
  a[915][26] = 0;
  a[916][26] = 0;
  a[917][26] = 0;
  a[918][26] = 0;
  a[919][26] = 0;
  a[920][26] = 0;
  a[921][26] = 0;
  a[922][26] = 0;
  a[923][26] = 0;
  a[924][26] = 0;
  a[925][26] = 0;
  a[926][26] = 0;
  a[927][26] = 0;
  a[928][26] = 0;
  a[929][26] = 0;
  a[930][26] = 0;
  a[931][26] = 0;
  a[932][26] = 0;
  a[933][26] = 0;
  a[934][26] = 0;
  a[935][26] = 0;
  a[936][26] = 0;
  a[937][26] = 0;
  a[938][26] = 0;
  a[939][26] = 0;
  a[940][26] = 0;
  a[941][26] = 0;
  a[942][26] = 0;
  a[943][26] = 0;
  a[944][26] = 0;
  a[945][26] = 0;
  a[946][26] = 0;
  a[947][26] = 0;
  a[948][26] = 0;
  a[949][26] = 0;
  a[950][26] = 0;
  a[951][26] = 0;
  a[952][26] = 0;
  a[953][26] = 0;
  a[954][26] = 0;
  a[955][26] = 0;
  a[956][26] = 0;
  a[957][26] = 0;
  a[958][26] = 0;
  a[959][26] = 0;
  a[960][26] = 0;
  a[961][26] = 0;
  a[962][26] = 0;
  a[963][26] = 0;
  a[964][26] = 0;
  a[965][26] = 0;
  a[966][26] = 0;
  a[967][26] = 0;
  a[968][26] = 0;
  a[969][26] = 0;
  a[970][26] = 0;
  a[971][26] = 0;
  a[972][26] = 0;
  a[973][26] = 0;
  a[974][26] = 0;
  a[975][26] = 0;
  a[976][26] = 0;
  a[977][26] = 0;
  a[978][26] = 0;
  a[979][26] = 0;
  a[980][26] = 0;
  a[981][26] = 0;
  a[982][26] = 0;
  a[983][26] = 0;
  a[984][26] = 0;
  a[985][26] = 0;
  a[986][26] = 0;
  a[987][26] = 0;
  a[988][26] = 0;
  a[989][26] = 0;
  a[990][26] = 0;
  a[991][26] = 0;
  a[992][26] = 0;
  a[993][26] = 0;
  a[994][26] = 0;
  a[995][26] = 0;
  a[996][26] = 0;
  a[997][26] = 0;
  a[998][26] = 0;
  a[999][26] = 0;
  a[1000][26] = 0;
  a[800][27] = 276054145;
  a[801][27] = 0;
  a[802][27] = 0;
  a[803][27] = 0;
  a[804][27] = 0;
  a[805][27] = 0;
  a[806][27] = 0;
  a[807][27] = 0;
  a[808][27] = 0;
  a[809][27] = 0;
  a[810][27] = 0;
  a[811][27] = 0;
  a[812][27] = 0;
  a[813][27] = 0;
  a[814][27] = 0;
  a[815][27] = 0;
  a[816][27] = 0;
  a[817][27] = 0;
  a[818][27] = 0;
  a[819][27] = 0;
  a[820][27] = 0;
  a[821][27] = 0;
  a[822][27] = 0;
  a[823][27] = 0;
  a[824][27] = 0;
  a[825][27] = 0;
  a[826][27] = 0;
  a[827][27] = 0;
  a[828][27] = 0;
  a[829][27] = 0;
  a[830][27] = 0;
  a[831][27] = 0;
  a[832][27] = 0;
  a[833][27] = 0;
  a[834][27] = 0;
  a[835][27] = 0;
  a[836][27] = 0;
  a[837][27] = 0;
  a[838][27] = 0;
  a[839][27] = 0;
  a[840][27] = 0;
  a[841][27] = 0;
  a[842][27] = 0;
  a[843][27] = 0;
  a[844][27] = 0;
  a[845][27] = 0;
  a[846][27] = 0;
  a[847][27] = 0;
  a[848][27] = 0;
  a[849][27] = 0;
  a[850][27] = 0;
  a[851][27] = 0;
  a[852][27] = 0;
  a[853][27] = 0;
  a[854][27] = 0;
  a[855][27] = 0;
  a[856][27] = 0;
  a[857][27] = 0;
  a[858][27] = 0;
  a[859][27] = 0;
  a[860][27] = 0;
  a[861][27] = 0;
  a[862][27] = 0;
  a[863][27] = 0;
  a[864][27] = 0;
  a[865][27] = 0;
  a[866][27] = 0;
  a[867][27] = 0;
  a[868][27] = 0;
  a[869][27] = 0;
  a[870][27] = 0;
  a[871][27] = 0;
  a[872][27] = 0;
  a[873][27] = 0;
  a[874][27] = 0;
  a[875][27] = 0;
  a[876][27] = 0;
  a[877][27] = 0;
  a[878][27] = 0;
  a[879][27] = 0;
  a[880][27] = 0;
  a[881][27] = 0;
  a[882][27] = 0;
  a[883][27] = 0;
  a[884][27] = 0;
  a[885][27] = 0;
  a[886][27] = 0;
  a[887][27] = 0;
  a[888][27] = 0;
  a[889][27] = 0;
  a[890][27] = 0;
  a[891][27] = 0;
  a[892][27] = 0;
  a[893][27] = 0;
  a[894][27] = 0;
  a[895][27] = 0;
  a[896][27] = 0;
  a[897][27] = 0;
  a[898][27] = 0;
  a[899][27] = 0;
  a[900][27] = 0;
  a[901][27] = 0;
  a[902][27] = 0;
  a[903][27] = 0;
  a[904][27] = 0;
  a[905][27] = 0;
  a[906][27] = 0;
  a[907][27] = 0;
  a[908][27] = 0;
  a[909][27] = 0;
  a[910][27] = 0;
  a[911][27] = 0;
  a[912][27] = 0;
  a[913][27] = 0;
  a[914][27] = 0;
  a[915][27] = 0;
  a[916][27] = 0;
  a[917][27] = 0;
  a[918][27] = 0;
  a[919][27] = 0;
  a[920][27] = 0;
  a[921][27] = 0;
  a[922][27] = 0;
  a[923][27] = 0;
  a[924][27] = 0;
  a[925][27] = 0;
  a[926][27] = 0;
  a[927][27] = 0;
  a[928][27] = 0;
  a[929][27] = 0;
  a[930][27] = 0;
  a[931][27] = 0;
  a[932][27] = 0;
  a[933][27] = 0;
  a[934][27] = 0;
  a[935][27] = 0;
  a[936][27] = 0;
  a[937][27] = 0;
  a[938][27] = 0;
  a[939][27] = 0;
  a[940][27] = 0;
  a[941][27] = 0;
  a[942][27] = 0;
  a[943][27] = 0;
  a[944][27] = 0;
  a[945][27] = 0;
  a[946][27] = 0;
  a[947][27] = 0;
  a[948][27] = 0;
  a[949][27] = 0;
  a[950][27] = 0;
  a[951][27] = 0;
  a[952][27] = 0;
  a[953][27] = 0;
  a[954][27] = 0;
  a[955][27] = 0;
  a[956][27] = 0;
  a[957][27] = 0;
  a[958][27] = 0;
  a[959][27] = 0;
  a[960][27] = 0;
  a[961][27] = 0;
  a[962][27] = 0;
  a[963][27] = 0;
  a[964][27] = 0;
  a[965][27] = 0;
  a[966][27] = 0;
  a[967][27] = 0;
  a[968][27] = 0;
  a[969][27] = 0;
  a[970][27] = 0;
  a[971][27] = 0;
  a[972][27] = 0;
  a[973][27] = 0;
  a[974][27] = 0;
  a[975][27] = 0;
  a[976][27] = 0;
  a[977][27] = 0;
  a[978][27] = 0;
  a[979][27] = 0;
  a[980][27] = 0;
  a[981][27] = 0;
  a[982][27] = 0;
  a[983][27] = 0;
  a[984][27] = 0;
  a[985][27] = 0;
  a[986][27] = 0;
  a[987][27] = 0;
  a[988][27] = 0;
  a[989][27] = 0;
  a[990][27] = 0;
  a[991][27] = 0;
  a[992][27] = 0;
  a[993][27] = 0;
  a[994][27] = 0;
  a[995][27] = 0;
  a[996][27] = 0;
  a[997][27] = 0;
  a[998][27] = 0;
  a[999][27] = 0;
  a[1000][27] = 0;
  a[800][28] = 981336826;
  a[801][28] = 0;
  a[802][28] = 0;
  a[803][28] = 0;
  a[804][28] = 0;
  a[805][28] = 0;
  a[806][28] = 0;
  a[807][28] = 0;
  a[808][28] = 0;
  a[809][28] = 0;
  a[810][28] = 0;
  a[811][28] = 0;
  a[812][28] = 0;
  a[813][28] = 0;
  a[814][28] = 0;
  a[815][28] = 0;
  a[816][28] = 0;
  a[817][28] = 0;
  a[818][28] = 0;
  a[819][28] = 0;
  a[820][28] = 0;
  a[821][28] = 0;
  a[822][28] = 0;
  a[823][28] = 0;
  a[824][28] = 0;
  a[825][28] = 0;
  a[826][28] = 0;
  a[827][28] = 0;
  a[828][28] = 0;
  a[829][28] = 0;
  a[830][28] = 0;
  a[831][28] = 0;
  a[832][28] = 0;
  a[833][28] = 0;
  a[834][28] = 0;
  a[835][28] = 0;
  a[836][28] = 0;
  a[837][28] = 0;
  a[838][28] = 0;
  a[839][28] = 0;
  a[840][28] = 0;
  a[841][28] = 0;
  a[842][28] = 0;
  a[843][28] = 0;
  a[844][28] = 0;
  a[845][28] = 0;
  a[846][28] = 0;
  a[847][28] = 0;
  a[848][28] = 0;
  a[849][28] = 0;
  a[850][28] = 0;
  a[851][28] = 0;
  a[852][28] = 0;
  a[853][28] = 0;
  a[854][28] = 0;
  a[855][28] = 0;
  a[856][28] = 0;
  a[857][28] = 0;
  a[858][28] = 0;
  a[859][28] = 0;
  a[860][28] = 0;
  a[861][28] = 0;
  a[862][28] = 0;
  a[863][28] = 0;
  a[864][28] = 0;
  a[865][28] = 0;
  a[866][28] = 0;
  a[867][28] = 0;
  a[868][28] = 0;
  a[869][28] = 0;
  a[870][28] = 0;
  a[871][28] = 0;
  a[872][28] = 0;
  a[873][28] = 0;
  a[874][28] = 0;
  a[875][28] = 0;
  a[876][28] = 0;
  a[877][28] = 0;
  a[878][28] = 0;
  a[879][28] = 0;
  a[880][28] = 0;
  a[881][28] = 0;
  a[882][28] = 0;
  a[883][28] = 0;
  a[884][28] = 0;
  a[885][28] = 0;
  a[886][28] = 0;
  a[887][28] = 0;
  a[888][28] = 0;
  a[889][28] = 0;
  a[890][28] = 0;
  a[891][28] = 0;
  a[892][28] = 0;
  a[893][28] = 0;
  a[894][28] = 0;
  a[895][28] = 0;
  a[896][28] = 0;
  a[897][28] = 0;
  a[898][28] = 0;
  a[899][28] = 0;
  a[900][28] = 0;
  a[901][28] = 0;
  a[902][28] = 0;
  a[903][28] = 0;
  a[904][28] = 0;
  a[905][28] = 0;
  a[906][28] = 0;
  a[907][28] = 0;
  a[908][28] = 0;
  a[909][28] = 0;
  a[910][28] = 0;
  a[911][28] = 0;
  a[912][28] = 0;
  a[913][28] = 0;
  a[914][28] = 0;
  a[915][28] = 0;
  a[916][28] = 0;
  a[917][28] = 0;
  a[918][28] = 0;
  a[919][28] = 0;
  a[920][28] = 0;
  a[921][28] = 0;
  a[922][28] = 0;
  a[923][28] = 0;
  a[924][28] = 0;
  a[925][28] = 0;
  a[926][28] = 0;
  a[927][28] = 0;
  a[928][28] = 0;
  a[929][28] = 0;
  a[930][28] = 0;
  a[931][28] = 0;
  a[932][28] = 0;
  a[933][28] = 0;
  a[934][28] = 0;
  a[935][28] = 0;
  a[936][28] = 0;
  a[937][28] = 0;
  a[938][28] = 0;
  a[939][28] = 0;
  a[940][28] = 0;
  a[941][28] = 0;
  a[942][28] = 0;
  a[943][28] = 0;
  a[944][28] = 0;
  a[945][28] = 0;
  a[946][28] = 0;
  a[947][28] = 0;
  a[948][28] = 0;
  a[949][28] = 0;
  a[950][28] = 0;
  a[951][28] = 0;
  a[952][28] = 0;
  a[953][28] = 0;
  a[954][28] = 0;
  a[955][28] = 0;
  a[956][28] = 0;
  a[957][28] = 0;
  a[958][28] = 0;
  a[959][28] = 0;
  a[960][28] = 0;
  a[961][28] = 0;
  a[962][28] = 0;
  a[963][28] = 0;
  a[964][28] = 0;
  a[965][28] = 0;
  a[966][28] = 0;
  a[967][28] = 0;
  a[968][28] = 0;
  a[969][28] = 0;
  a[970][28] = 0;
  a[971][28] = 0;
  a[972][28] = 0;
  a[973][28] = 0;
  a[974][28] = 0;
  a[975][28] = 0;
  a[976][28] = 0;
  a[977][28] = 0;
  a[978][28] = 0;
  a[979][28] = 0;
  a[980][28] = 0;
  a[981][28] = 0;
  a[982][28] = 0;
  a[983][28] = 0;
  a[984][28] = 0;
  a[985][28] = 0;
  a[986][28] = 0;
  a[987][28] = 0;
  a[988][28] = 0;
  a[989][28] = 0;
  a[990][28] = 0;
  a[991][28] = 0;
  a[992][28] = 0;
  a[993][28] = 0;
  a[994][28] = 0;
  a[995][28] = 0;
  a[996][28] = 0;
  a[997][28] = 0;
  a[998][28] = 0;
  a[999][28] = 0;
  a[1000][28] = 0;
  a[800][29] = 21504211;
  a[801][29] = 0;
  a[802][29] = 0;
  a[803][29] = 0;
  a[804][29] = 0;
  a[805][29] = 0;
  a[806][29] = 0;
  a[807][29] = 0;
  a[808][29] = 0;
  a[809][29] = 0;
  a[810][29] = 0;
  a[811][29] = 0;
  a[812][29] = 0;
  a[813][29] = 0;
  a[814][29] = 0;
  a[815][29] = 0;
  a[816][29] = 0;
  a[817][29] = 0;
  a[818][29] = 0;
  a[819][29] = 0;
  a[820][29] = 0;
  a[821][29] = 0;
  a[822][29] = 0;
  a[823][29] = 0;
  a[824][29] = 0;
  a[825][29] = 0;
  a[826][29] = 0;
  a[827][29] = 0;
  a[828][29] = 0;
  a[829][29] = 0;
  a[830][29] = 0;
  a[831][29] = 0;
  a[832][29] = 0;
  a[833][29] = 0;
  a[834][29] = 0;
  a[835][29] = 0;
  a[836][29] = 0;
  a[837][29] = 0;
  a[838][29] = 0;
  a[839][29] = 0;
  a[840][29] = 0;
  a[841][29] = 0;
  a[842][29] = 0;
  a[843][29] = 0;
  a[844][29] = 0;
  a[845][29] = 0;
  a[846][29] = 0;
  a[847][29] = 0;
  a[848][29] = 0;
  a[849][29] = 0;
  a[850][29] = 0;
  a[851][29] = 0;
  a[852][29] = 0;
  a[853][29] = 0;
  a[854][29] = 0;
  a[855][29] = 0;
  a[856][29] = 0;
  a[857][29] = 0;
  a[858][29] = 0;
  a[859][29] = 0;
  a[860][29] = 0;
  a[861][29] = 0;
  a[862][29] = 0;
  a[863][29] = 0;
  a[864][29] = 0;
  a[865][29] = 0;
  a[866][29] = 0;
  a[867][29] = 0;
  a[868][29] = 0;
  a[869][29] = 0;
  a[870][29] = 0;
  a[871][29] = 0;
  a[872][29] = 0;
  a[873][29] = 0;
  a[874][29] = 0;
  a[875][29] = 0;
  a[876][29] = 0;
  a[877][29] = 0;
  a[878][29] = 0;
  a[879][29] = 0;
  a[880][29] = 0;
  a[881][29] = 0;
  a[882][29] = 0;
  a[883][29] = 0;
  a[884][29] = 0;
  a[885][29] = 0;
  a[886][29] = 0;
  a[887][29] = 0;
  a[888][29] = 0;
  a[889][29] = 0;
  a[890][29] = 0;
  a[891][29] = 0;
  a[892][29] = 0;
  a[893][29] = 0;
  a[894][29] = 0;
  a[895][29] = 0;
  a[896][29] = 0;
  a[897][29] = 0;
  a[898][29] = 0;
  a[899][29] = 0;
  a[900][29] = 0;
  a[901][29] = 0;
  a[902][29] = 0;
  a[903][29] = 0;
  a[904][29] = 0;
  a[905][29] = 0;
  a[906][29] = 0;
  a[907][29] = 0;
  a[908][29] = 0;
  a[909][29] = 0;
  a[910][29] = 0;
  a[911][29] = 0;
  a[912][29] = 0;
  a[913][29] = 0;
  a[914][29] = 0;
  a[915][29] = 0;
  a[916][29] = 0;
  a[917][29] = 0;
  a[918][29] = 0;
  a[919][29] = 0;
  a[920][29] = 0;
  a[921][29] = 0;
  a[922][29] = 0;
  a[923][29] = 0;
  a[924][29] = 0;
  a[925][29] = 0;
  a[926][29] = 0;
  a[927][29] = 0;
  a[928][29] = 0;
  a[929][29] = 0;
  a[930][29] = 0;
  a[931][29] = 0;
  a[932][29] = 0;
  a[933][29] = 0;
  a[934][29] = 0;
  a[935][29] = 0;
  a[936][29] = 0;
  a[937][29] = 0;
  a[938][29] = 0;
  a[939][29] = 0;
  a[940][29] = 0;
  a[941][29] = 0;
  a[942][29] = 0;
  a[943][29] = 0;
  a[944][29] = 0;
  a[945][29] = 0;
  a[946][29] = 0;
  a[947][29] = 0;
  a[948][29] = 0;
  a[949][29] = 0;
  a[950][29] = 0;
  a[951][29] = 0;
  a[952][29] = 0;
  a[953][29] = 0;
  a[954][29] = 0;
  a[955][29] = 0;
  a[956][29] = 0;
  a[957][29] = 0;
  a[958][29] = 0;
  a[959][29] = 0;
  a[960][29] = 0;
  a[961][29] = 0;
  a[962][29] = 0;
  a[963][29] = 0;
  a[964][29] = 0;
  a[965][29] = 0;
  a[966][29] = 0;
  a[967][29] = 0;
  a[968][29] = 0;
  a[969][29] = 0;
  a[970][29] = 0;
  a[971][29] = 0;
  a[972][29] = 0;
  a[973][29] = 0;
  a[974][29] = 0;
  a[975][29] = 0;
  a[976][29] = 0;
  a[977][29] = 0;
  a[978][29] = 0;
  a[979][29] = 0;
  a[980][29] = 0;
  a[981][29] = 0;
  a[982][29] = 0;
  a[983][29] = 0;
  a[984][29] = 0;
  a[985][29] = 0;
  a[986][29] = 0;
  a[987][29] = 0;
  a[988][29] = 0;
  a[989][29] = 0;
  a[990][29] = 0;
  a[991][29] = 0;
  a[992][29] = 0;
  a[993][29] = 0;
  a[994][29] = 0;
  a[995][29] = 0;
  a[996][29] = 0;
  a[997][29] = 0;
  a[998][29] = 0;
  a[999][29] = 0;
  a[1000][29] = 0;
  a[800][30] = 352119519;
  a[801][30] = 0;
  a[802][30] = 0;
  a[803][30] = 0;
  a[804][30] = 0;
  a[805][30] = 0;
  a[806][30] = 0;
  a[807][30] = 0;
  a[808][30] = 0;
  a[809][30] = 0;
  a[810][30] = 0;
  a[811][30] = 0;
  a[812][30] = 0;
  a[813][30] = 0;
  a[814][30] = 0;
  a[815][30] = 0;
  a[816][30] = 0;
  a[817][30] = 0;
  a[818][30] = 0;
  a[819][30] = 0;
  a[820][30] = 0;
  a[821][30] = 0;
  a[822][30] = 0;
  a[823][30] = 0;
  a[824][30] = 0;
  a[825][30] = 0;
  a[826][30] = 0;
  a[827][30] = 0;
  a[828][30] = 0;
  a[829][30] = 0;
  a[830][30] = 0;
  a[831][30] = 0;
  a[832][30] = 0;
  a[833][30] = 0;
  a[834][30] = 0;
  a[835][30] = 0;
  a[836][30] = 0;
  a[837][30] = 0;
  a[838][30] = 0;
  a[839][30] = 0;
  a[840][30] = 0;
  a[841][30] = 0;
  a[842][30] = 0;
  a[843][30] = 0;
  a[844][30] = 0;
  a[845][30] = 0;
  a[846][30] = 0;
  a[847][30] = 0;
  a[848][30] = 0;
  a[849][30] = 0;
  a[850][30] = 0;
  a[851][30] = 0;
  a[852][30] = 0;
  a[853][30] = 0;
  a[854][30] = 0;
  a[855][30] = 0;
  a[856][30] = 0;
  a[857][30] = 0;
  a[858][30] = 0;
  a[859][30] = 0;
  a[860][30] = 0;
  a[861][30] = 0;
  a[862][30] = 0;
  a[863][30] = 0;
  a[864][30] = 0;
  a[865][30] = 0;
  a[866][30] = 0;
  a[867][30] = 0;
  a[868][30] = 0;
  a[869][30] = 0;
  a[870][30] = 0;
  a[871][30] = 0;
  a[872][30] = 0;
  a[873][30] = 0;
  a[874][30] = 0;
  a[875][30] = 0;
  a[876][30] = 0;
  a[877][30] = 0;
  a[878][30] = 0;
  a[879][30] = 0;
  a[880][30] = 0;
  a[881][30] = 0;
  a[882][30] = 0;
  a[883][30] = 0;
  a[884][30] = 0;
  a[885][30] = 0;
  a[886][30] = 0;
  a[887][30] = 0;
  a[888][30] = 0;
  a[889][30] = 0;
  a[890][30] = 0;
  a[891][30] = 0;
  a[892][30] = 0;
  a[893][30] = 0;
  a[894][30] = 0;
  a[895][30] = 0;
  a[896][30] = 0;
  a[897][30] = 0;
  a[898][30] = 0;
  a[899][30] = 0;
  a[900][30] = 0;
  a[901][30] = 0;
  a[902][30] = 0;
  a[903][30] = 0;
  a[904][30] = 0;
  a[905][30] = 0;
  a[906][30] = 0;
  a[907][30] = 0;
  a[908][30] = 0;
  a[909][30] = 0;
  a[910][30] = 0;
  a[911][30] = 0;
  a[912][30] = 0;
  a[913][30] = 0;
  a[914][30] = 0;
  a[915][30] = 0;
  a[916][30] = 0;
  a[917][30] = 0;
  a[918][30] = 0;
  a[919][30] = 0;
  a[920][30] = 0;
  a[921][30] = 0;
  a[922][30] = 0;
  a[923][30] = 0;
  a[924][30] = 0;
  a[925][30] = 0;
  a[926][30] = 0;
  a[927][30] = 0;
  a[928][30] = 0;
  a[929][30] = 0;
  a[930][30] = 0;
  a[931][30] = 0;
  a[932][30] = 0;
  a[933][30] = 0;
  a[934][30] = 0;
  a[935][30] = 0;
  a[936][30] = 0;
  a[937][30] = 0;
  a[938][30] = 0;
  a[939][30] = 0;
  a[940][30] = 0;
  a[941][30] = 0;
  a[942][30] = 0;
  a[943][30] = 0;
  a[944][30] = 0;
  a[945][30] = 0;
  a[946][30] = 0;
  a[947][30] = 0;
  a[948][30] = 0;
  a[949][30] = 0;
  a[950][30] = 0;
  a[951][30] = 0;
  a[952][30] = 0;
  a[953][30] = 0;
  a[954][30] = 0;
  a[955][30] = 0;
  a[956][30] = 0;
  a[957][30] = 0;
  a[958][30] = 0;
  a[959][30] = 0;
  a[960][30] = 0;
  a[961][30] = 0;
  a[962][30] = 0;
  a[963][30] = 0;
  a[964][30] = 0;
  a[965][30] = 0;
  a[966][30] = 0;
  a[967][30] = 0;
  a[968][30] = 0;
  a[969][30] = 0;
  a[970][30] = 0;
  a[971][30] = 0;
  a[972][30] = 0;
  a[973][30] = 0;
  a[974][30] = 0;
  a[975][30] = 0;
  a[976][30] = 0;
  a[977][30] = 0;
  a[978][30] = 0;
  a[979][30] = 0;
  a[980][30] = 0;
  a[981][30] = 0;
  a[982][30] = 0;
  a[983][30] = 0;
  a[984][30] = 0;
  a[985][30] = 0;
  a[986][30] = 0;
  a[987][30] = 0;
  a[988][30] = 0;
  a[989][30] = 0;
  a[990][30] = 0;
  a[991][30] = 0;
  a[992][30] = 0;
  a[993][30] = 0;
  a[994][30] = 0;
  a[995][30] = 0;
  a[996][30] = 0;
  a[997][30] = 0;
  a[998][30] = 0;
  a[999][30] = 0;
  a[1000][30] = 0;
}
int main() {
  prepare();
  int i, j, u, v, w, o, x, y, z, ad;
  rdi(n), rdi(h);
  if (a[n][h]) {
    print(a[n][h]);
    return 0;
  }
  dp[0][2][2][2][1] = 1;
  for (i = 1; i < n; ++i) {
    for (x = 2; x < h + 2; ++x) {
      for (y = x; y < h + 2; ++y) {
        for (z = y; z < h + 2; ++z) {
          for (o = 0; o < 2; ++o) {
            ad = dp[i - 1][x][y][z][o];
            if (!ad) continue;
            u = x > h ? x : x + 1;
            v = y > h ? y : y + 1;
            w = z > h ? z : z + 1;
            add(dp[i][u][v][w][o], ad);
            if (o) {
              add(dp[i][2][v][w][x <= h], ad);
              add(dp[i][2][u][w][y <= h], ad);
              add(dp[i][2][u][v][z <= h], ad);
            } else {
              add(dp[i][v][w][h + 1][x <= h], ad);
              add(dp[i][u][w][h + 1][y <= h], ad);
              add(dp[i][u][v][h + 1][z <= h], ad);
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (x = 0; x < h + 2; ++x)
    for (y = 0; y < h + 2; ++y)
      for (z = 0; z < h + 2; ++z)
        for (o = 0; o < 2; ++o)
          if (x <= h or y <= h or z <= h or o) add(ans, dp[n - 1][x][y][z][o]);
  ans = (long long)(ans * 4ll) % md;
  print(ans);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Manao is working for a construction company. Recently, an order came to build wall bars in a children's park. Manao was commissioned to develop a plan of construction, which will enable the company to save the most money.

After reviewing the formal specifications for the wall bars, Manao discovered a number of controversial requirements and decided to treat them to the company's advantage. His resulting design can be described as follows:

  * Let's introduce some unit of length. The construction center is a pole of height n. 
  * At heights 1, 2, ..., n exactly one horizontal bar sticks out from the pole. Each bar sticks in one of four pre-fixed directions. 
  * A child can move from one bar to another if the distance between them does not exceed h and they stick in the same direction. If a child is on the ground, he can climb onto any of the bars at height between 1 and h. In Manao's construction a child should be able to reach at least one of the bars at heights n - h + 1, n - h + 2, ..., n if he begins at the ground. 

<image> The figure to the left shows what a common set of wall bars looks like. The figure to the right shows Manao's construction

Manao is wondering how many distinct construction designs that satisfy his requirements exist. As this number can be rather large, print the remainder after dividing it by 1000000009 (109 + 9). Two designs are considered distinct if there is such height i, that the bars on the height i in these designs don't stick out in the same direction.

Input

A single line contains two space-separated integers, n and h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(n, 30)).

Output

In a single line print the remainder after dividing the number of designs by 1000000009 (109 + 9).

Examples

Input

5 1


Output

4


Input

4 2


Output

148


Input

4 3


Output

256


Input

5 2


Output

376

Note

Consider several designs for h = 2. A design with the first bar sticked out in direction d1, the second — in direction d2 and so on (1 ≤ di ≤ 4) is denoted as string d1d2...dn.

Design "1231" (the first three bars are sticked out in different directions, the last one — in the same as first). A child can reach neither the bar at height 3 nor the bar at height 4.

Design "414141". A child can reach the bar at height 5. To do this, he should first climb at the first bar, then at the third and then at the fifth one. He can also reach bar at height 6 by the route second  →  fourth  →  sixth bars.

Design "123333". The child can't reach the upper two bars.

Design "323323". The bar at height 6 can be reached by the following route: first  →  third  →  fourth  →  sixth bars.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
using namespace std;
inline void rdl(long long &val) {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline void rdi(int &val) {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  val = x * f;
}
inline long long rdl() {
  long long x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline int rdi() {
  int x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' or ch > '9') and ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void _write(int x) {
  write(x);
  putchar(' ');
}
inline void print(int x) {
  write(x);
  putchar('\n');
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void _write(long long x) {
  write(x);
  putchar(' ');
}
inline void print(long long x) {
  write(x);
  putchar('\n');
}
struct dsu {
  int par[200200];
  inline void init(int _n) {
    for (int i = 0; i < _n; ++i) par[i] = i;
  }
  inline int find(int now) {
    if (par[now] == now) return now;
    return par[now] = find(par[now]);
  }
  inline bool uni(int a, int b) {
    int Pa(find(a)), Pb(find(b));
    if (Pa == Pb) return false;
    par[Pa] = Pb;
    return true;
  }
};
const int md = 1000000009;
inline void add(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
int dp[1001][33][33][33][2], n, h;
int a[1001][33];
inline void prepare() {
  a[800][20] = 539577677;
  a[801][20] = 0;
  a[802][20] = 0;
  a[803][20] = 0;
  a[804][20] = 0;
  a[805][20] = 0;
  a[806][20] = 0;
  a[807][20] = 0;
  a[808][20] = 0;
  a[809][20] = 0;
  a[810][20] = 0;
  a[811][20] = 0;
  a[812][20] = 0;
  a[813][20] = 0;
  a[814][20] = 0;
  a[815][20] = 0;
  a[816][20] = 0;
  a[817][20] = 0;
  a[818][20] = 0;
  a[819][20] = 0;
  a[820][20] = 0;
  a[821][20] = 0;
  a[822][20] = 0;
  a[823][20] = 0;
  a[824][20] = 0;
  a[825][20] = 0;
  a[826][20] = 0;
  a[827][20] = 0;
  a[828][20] = 0;
  a[829][20] = 0;
  a[830][20] = 0;
  a[831][20] = 0;
  a[832][20] = 0;
  a[833][20] = 0;
  a[834][20] = 0;
  a[835][20] = 0;
  a[836][20] = 0;
  a[837][20] = 0;
  a[838][20] = 0;
  a[839][20] = 0;
  a[840][20] = 0;
  a[841][20] = 0;
  a[842][20] = 0;
  a[843][20] = 0;
  a[844][20] = 0;
  a[845][20] = 0;
  a[846][20] = 0;
  a[847][20] = 0;
  a[848][20] = 0;
  a[849][20] = 0;
  a[850][20] = 0;
  a[851][20] = 0;
  a[852][20] = 0;
  a[853][20] = 0;
  a[854][20] = 0;
  a[855][20] = 0;
  a[856][20] = 0;
  a[857][20] = 0;
  a[858][20] = 0;
  a[859][20] = 0;
  a[860][20] = 0;
  a[861][20] = 0;
  a[862][20] = 0;
  a[863][20] = 0;
  a[864][20] = 0;
  a[865][20] = 0;
  a[866][20] = 0;
  a[867][20] = 0;
  a[868][20] = 0;
  a[869][20] = 0;
  a[870][20] = 0;
  a[871][20] = 0;
  a[872][20] = 0;
  a[873][20] = 0;
  a[874][20] = 0;
  a[875][20] = 0;
  a[876][20] = 0;
  a[877][20] = 0;
  a[878][20] = 0;
  a[879][20] = 0;
  a[880][20] = 0;
  a[881][20] = 0;
  a[882][20] = 0;
  a[883][20] = 0;
  a[884][20] = 0;
  a[885][20] = 0;
  a[886][20] = 0;
  a[887][20] = 0;
  a[888][20] = 0;
  a[889][20] = 0;
  a[890][20] = 0;
  a[891][20] = 0;
  a[892][20] = 0;
  a[893][20] = 0;
  a[894][20] = 0;
  a[895][20] = 0;
  a[896][20] = 0;
  a[897][20] = 0;
  a[898][20] = 0;
  a[899][20] = 0;
  a[900][20] = 0;
  a[901][20] = 0;
  a[902][20] = 0;
  a[903][20] = 0;
  a[904][20] = 0;
  a[905][20] = 0;
  a[906][20] = 0;
  a[907][20] = 0;
  a[908][20] = 0;
  a[909][20] = 0;
  a[910][20] = 0;
  a[911][20] = 0;
  a[912][20] = 0;
  a[913][20] = 0;
  a[914][20] = 0;
  a[915][20] = 0;
  a[916][20] = 0;
  a[917][20] = 0;
  a[918][20] = 0;
  a[919][20] = 0;
  a[920][20] = 0;
  a[921][20] = 0;
  a[922][20] = 0;
  a[923][20] = 0;
  a[924][20] = 0;
  a[925][20] = 0;
  a[926][20] = 0;
  a[927][20] = 0;
  a[928][20] = 0;
  a[929][20] = 0;
  a[930][20] = 0;
  a[931][20] = 0;
  a[932][20] = 0;
  a[933][20] = 0;
  a[934][20] = 0;
  a[935][20] = 0;
  a[936][20] = 0;
  a[937][20] = 0;
  a[938][20] = 0;
  a[939][20] = 0;
  a[940][20] = 0;
  a[941][20] = 0;
  a[942][20] = 0;
  a[943][20] = 0;
  a[944][20] = 0;
  a[945][20] = 0;
  a[946][20] = 0;
  a[947][20] = 0;
  a[948][20] = 0;
  a[949][20] = 0;
  a[950][20] = 0;
  a[951][20] = 0;
  a[952][20] = 0;
  a[953][20] = 0;
  a[954][20] = 0;
  a[955][20] = 0;
  a[956][20] = 0;
  a[957][20] = 0;
  a[958][20] = 0;
  a[959][20] = 0;
  a[960][20] = 0;
  a[961][20] = 0;
  a[962][20] = 0;
  a[963][20] = 0;
  a[964][20] = 0;
  a[965][20] = 0;
  a[966][20] = 0;
  a[967][20] = 0;
  a[968][20] = 0;
  a[969][20] = 0;
  a[970][20] = 0;
  a[971][20] = 0;
  a[972][20] = 0;
  a[973][20] = 0;
  a[974][20] = 0;
  a[975][20] = 0;
  a[976][20] = 0;
  a[977][20] = 0;
  a[978][20] = 0;
  a[979][20] = 0;
  a[980][20] = 0;
  a[981][20] = 0;
  a[982][20] = 0;
  a[983][20] = 0;
  a[984][20] = 0;
  a[985][20] = 0;
  a[986][20] = 0;
  a[987][20] = 0;
  a[988][20] = 0;
  a[989][20] = 0;
  a[990][20] = 0;
  a[991][20] = 0;
  a[992][20] = 0;
  a[993][20] = 0;
  a[994][20] = 0;
  a[995][20] = 0;
  a[996][20] = 0;
  a[997][20] = 0;
  a[998][20] = 0;
  a[999][20] = 0;
  a[1000][20] = 0;
  a[800][21] = 419889129;
  a[801][21] = 0;
  a[802][21] = 0;
  a[803][21] = 0;
  a[804][21] = 0;
  a[805][21] = 0;
  a[806][21] = 0;
  a[807][21] = 0;
  a[808][21] = 0;
  a[809][21] = 0;
  a[810][21] = 0;
  a[811][21] = 0;
  a[812][21] = 0;
  a[813][21] = 0;
  a[814][21] = 0;
  a[815][21] = 0;
  a[816][21] = 0;
  a[817][21] = 0;
  a[818][21] = 0;
  a[819][21] = 0;
  a[820][21] = 0;
  a[821][21] = 0;
  a[822][21] = 0;
  a[823][21] = 0;
  a[824][21] = 0;
  a[825][21] = 0;
  a[826][21] = 0;
  a[827][21] = 0;
  a[828][21] = 0;
  a[829][21] = 0;
  a[830][21] = 0;
  a[831][21] = 0;
  a[832][21] = 0;
  a[833][21] = 0;
  a[834][21] = 0;
  a[835][21] = 0;
  a[836][21] = 0;
  a[837][21] = 0;
  a[838][21] = 0;
  a[839][21] = 0;
  a[840][21] = 0;
  a[841][21] = 0;
  a[842][21] = 0;
  a[843][21] = 0;
  a[844][21] = 0;
  a[845][21] = 0;
  a[846][21] = 0;
  a[847][21] = 0;
  a[848][21] = 0;
  a[849][21] = 0;
  a[850][21] = 0;
  a[851][21] = 0;
  a[852][21] = 0;
  a[853][21] = 0;
  a[854][21] = 0;
  a[855][21] = 0;
  a[856][21] = 0;
  a[857][21] = 0;
  a[858][21] = 0;
  a[859][21] = 0;
  a[860][21] = 0;
  a[861][21] = 0;
  a[862][21] = 0;
  a[863][21] = 0;
  a[864][21] = 0;
  a[865][21] = 0;
  a[866][21] = 0;
  a[867][21] = 0;
  a[868][21] = 0;
  a[869][21] = 0;
  a[870][21] = 0;
  a[871][21] = 0;
  a[872][21] = 0;
  a[873][21] = 0;
  a[874][21] = 0;
  a[875][21] = 0;
  a[876][21] = 0;
  a[877][21] = 0;
  a[878][21] = 0;
  a[879][21] = 0;
  a[880][21] = 0;
  a[881][21] = 0;
  a[882][21] = 0;
  a[883][21] = 0;
  a[884][21] = 0;
  a[885][21] = 0;
  a[886][21] = 0;
  a[887][21] = 0;
  a[888][21] = 0;
  a[889][21] = 0;
  a[890][21] = 0;
  a[891][21] = 0;
  a[892][21] = 0;
  a[893][21] = 0;
  a[894][21] = 0;
  a[895][21] = 0;
  a[896][21] = 0;
  a[897][21] = 0;
  a[898][21] = 0;
  a[899][21] = 0;
  a[900][21] = 0;
  a[901][21] = 0;
  a[902][21] = 0;
  a[903][21] = 0;
  a[904][21] = 0;
  a[905][21] = 0;
  a[906][21] = 0;
  a[907][21] = 0;
  a[908][21] = 0;
  a[909][21] = 0;
  a[910][21] = 0;
  a[911][21] = 0;
  a[912][21] = 0;
  a[913][21] = 0;
  a[914][21] = 0;
  a[915][21] = 0;
  a[916][21] = 0;
  a[917][21] = 0;
  a[918][21] = 0;
  a[919][21] = 0;
  a[920][21] = 0;
  a[921][21] = 0;
  a[922][21] = 0;
  a[923][21] = 0;
  a[924][21] = 0;
  a[925][21] = 0;
  a[926][21] = 0;
  a[927][21] = 0;
  a[928][21] = 0;
  a[929][21] = 0;
  a[930][21] = 0;
  a[931][21] = 0;
  a[932][21] = 0;
  a[933][21] = 0;
  a[934][21] = 0;
  a[935][21] = 0;
  a[936][21] = 0;
  a[937][21] = 0;
  a[938][21] = 0;
  a[939][21] = 0;
  a[940][21] = 0;
  a[941][21] = 0;
  a[942][21] = 0;
  a[943][21] = 0;
  a[944][21] = 0;
  a[945][21] = 0;
  a[946][21] = 0;
  a[947][21] = 0;
  a[948][21] = 0;
  a[949][21] = 0;
  a[950][21] = 0;
  a[951][21] = 0;
  a[952][21] = 0;
  a[953][21] = 0;
  a[954][21] = 0;
  a[955][21] = 0;
  a[956][21] = 0;
  a[957][21] = 0;
  a[958][21] = 0;
  a[959][21] = 0;
  a[960][21] = 0;
  a[961][21] = 0;
  a[962][21] = 0;
  a[963][21] = 0;
  a[964][21] = 0;
  a[965][21] = 0;
  a[966][21] = 0;
  a[967][21] = 0;
  a[968][21] = 0;
  a[969][21] = 0;
  a[970][21] = 0;
  a[971][21] = 0;
  a[972][21] = 0;
  a[973][21] = 0;
  a[974][21] = 0;
  a[975][21] = 0;
  a[976][21] = 0;
  a[977][21] = 0;
  a[978][21] = 0;
  a[979][21] = 0;
  a[980][21] = 0;
  a[981][21] = 0;
  a[982][21] = 0;
  a[983][21] = 0;
  a[984][21] = 0;
  a[985][21] = 0;
  a[986][21] = 0;
  a[987][21] = 0;
  a[988][21] = 0;
  a[989][21] = 0;
  a[990][21] = 0;
  a[991][21] = 0;
  a[992][21] = 0;
  a[993][21] = 0;
  a[994][21] = 0;
  a[995][21] = 0;
  a[996][21] = 0;
  a[997][21] = 0;
  a[998][21] = 0;
  a[999][21] = 0;
  a[1000][21] = 0;
  a[800][22] = 322148007;
  a[801][22] = 0;
  a[802][22] = 0;
  a[803][22] = 0;
  a[804][22] = 0;
  a[805][22] = 0;
  a[806][22] = 0;
  a[807][22] = 0;
  a[808][22] = 0;
  a[809][22] = 0;
  a[810][22] = 0;
  a[811][22] = 0;
  a[812][22] = 0;
  a[813][22] = 0;
  a[814][22] = 0;
  a[815][22] = 0;
  a[816][22] = 0;
  a[817][22] = 0;
  a[818][22] = 0;
  a[819][22] = 0;
  a[820][22] = 0;
  a[821][22] = 0;
  a[822][22] = 0;
  a[823][22] = 0;
  a[824][22] = 0;
  a[825][22] = 0;
  a[826][22] = 0;
  a[827][22] = 0;
  a[828][22] = 0;
  a[829][22] = 0;
  a[830][22] = 0;
  a[831][22] = 0;
  a[832][22] = 0;
  a[833][22] = 0;
  a[834][22] = 0;
  a[835][22] = 0;
  a[836][22] = 0;
  a[837][22] = 0;
  a[838][22] = 0;
  a[839][22] = 0;
  a[840][22] = 0;
  a[841][22] = 0;
  a[842][22] = 0;
  a[843][22] = 0;
  a[844][22] = 0;
  a[845][22] = 0;
  a[846][22] = 0;
  a[847][22] = 0;
  a[848][22] = 0;
  a[849][22] = 0;
  a[850][22] = 0;
  a[851][22] = 0;
  a[852][22] = 0;
  a[853][22] = 0;
  a[854][22] = 0;
  a[855][22] = 0;
  a[856][22] = 0;
  a[857][22] = 0;
  a[858][22] = 0;
  a[859][22] = 0;
  a[860][22] = 0;
  a[861][22] = 0;
  a[862][22] = 0;
  a[863][22] = 0;
  a[864][22] = 0;
  a[865][22] = 0;
  a[866][22] = 0;
  a[867][22] = 0;
  a[868][22] = 0;
  a[869][22] = 0;
  a[870][22] = 0;
  a[871][22] = 0;
  a[872][22] = 0;
  a[873][22] = 0;
  a[874][22] = 0;
  a[875][22] = 0;
  a[876][22] = 0;
  a[877][22] = 0;
  a[878][22] = 0;
  a[879][22] = 0;
  a[880][22] = 0;
  a[881][22] = 0;
  a[882][22] = 0;
  a[883][22] = 0;
  a[884][22] = 0;
  a[885][22] = 0;
  a[886][22] = 0;
  a[887][22] = 0;
  a[888][22] = 0;
  a[889][22] = 0;
  a[890][22] = 0;
  a[891][22] = 0;
  a[892][22] = 0;
  a[893][22] = 0;
  a[894][22] = 0;
  a[895][22] = 0;
  a[896][22] = 0;
  a[897][22] = 0;
  a[898][22] = 0;
  a[899][22] = 0;
  a[900][22] = 0;
  a[901][22] = 0;
  a[902][22] = 0;
  a[903][22] = 0;
  a[904][22] = 0;
  a[905][22] = 0;
  a[906][22] = 0;
  a[907][22] = 0;
  a[908][22] = 0;
  a[909][22] = 0;
  a[910][22] = 0;
  a[911][22] = 0;
  a[912][22] = 0;
  a[913][22] = 0;
  a[914][22] = 0;
  a[915][22] = 0;
  a[916][22] = 0;
  a[917][22] = 0;
  a[918][22] = 0;
  a[919][22] = 0;
  a[920][22] = 0;
  a[921][22] = 0;
  a[922][22] = 0;
  a[923][22] = 0;
  a[924][22] = 0;
  a[925][22] = 0;
  a[926][22] = 0;
  a[927][22] = 0;
  a[928][22] = 0;
  a[929][22] = 0;
  a[930][22] = 0;
  a[931][22] = 0;
  a[932][22] = 0;
  a[933][22] = 0;
  a[934][22] = 0;
  a[935][22] = 0;
  a[936][22] = 0;
  a[937][22] = 0;
  a[938][22] = 0;
  a[939][22] = 0;
  a[940][22] = 0;
  a[941][22] = 0;
  a[942][22] = 0;
  a[943][22] = 0;
  a[944][22] = 0;
  a[945][22] = 0;
  a[946][22] = 0;
  a[947][22] = 0;
  a[948][22] = 0;
  a[949][22] = 0;
  a[950][22] = 0;
  a[951][22] = 0;
  a[952][22] = 0;
  a[953][22] = 0;
  a[954][22] = 0;
  a[955][22] = 0;
  a[956][22] = 0;
  a[957][22] = 0;
  a[958][22] = 0;
  a[959][22] = 0;
  a[960][22] = 0;
  a[961][22] = 0;
  a[962][22] = 0;
  a[963][22] = 0;
  a[964][22] = 0;
  a[965][22] = 0;
  a[966][22] = 0;
  a[967][22] = 0;
  a[968][22] = 0;
  a[969][22] = 0;
  a[970][22] = 0;
  a[971][22] = 0;
  a[972][22] = 0;
  a[973][22] = 0;
  a[974][22] = 0;
  a[975][22] = 0;
  a[976][22] = 0;
  a[977][22] = 0;
  a[978][22] = 0;
  a[979][22] = 0;
  a[980][22] = 0;
  a[981][22] = 0;
  a[982][22] = 0;
  a[983][22] = 0;
  a[984][22] = 0;
  a[985][22] = 0;
  a[986][22] = 0;
  a[987][22] = 0;
  a[988][22] = 0;
  a[989][22] = 0;
  a[990][22] = 0;
  a[991][22] = 0;
  a[992][22] = 0;
  a[993][22] = 0;
  a[994][22] = 0;
  a[995][22] = 0;
  a[996][22] = 0;
  a[997][22] = 0;
  a[998][22] = 0;
  a[999][22] = 0;
  a[1000][22] = 0;
  a[800][23] = 967760392;
  a[801][23] = 0;
  a[802][23] = 0;
  a[803][23] = 0;
  a[804][23] = 0;
  a[805][23] = 0;
  a[806][23] = 0;
  a[807][23] = 0;
  a[808][23] = 0;
  a[809][23] = 0;
  a[810][23] = 0;
  a[811][23] = 0;
  a[812][23] = 0;
  a[813][23] = 0;
  a[814][23] = 0;
  a[815][23] = 0;
  a[816][23] = 0;
  a[817][23] = 0;
  a[818][23] = 0;
  a[819][23] = 0;
  a[820][23] = 0;
  a[821][23] = 0;
  a[822][23] = 0;
  a[823][23] = 0;
  a[824][23] = 0;
  a[825][23] = 0;
  a[826][23] = 0;
  a[827][23] = 0;
  a[828][23] = 0;
  a[829][23] = 0;
  a[830][23] = 0;
  a[831][23] = 0;
  a[832][23] = 0;
  a[833][23] = 0;
  a[834][23] = 0;
  a[835][23] = 0;
  a[836][23] = 0;
  a[837][23] = 0;
  a[838][23] = 0;
  a[839][23] = 0;
  a[840][23] = 0;
  a[841][23] = 0;
  a[842][23] = 0;
  a[843][23] = 0;
  a[844][23] = 0;
  a[845][23] = 0;
  a[846][23] = 0;
  a[847][23] = 0;
  a[848][23] = 0;
  a[849][23] = 0;
  a[850][23] = 0;
  a[851][23] = 0;
  a[852][23] = 0;
  a[853][23] = 0;
  a[854][23] = 0;
  a[855][23] = 0;
  a[856][23] = 0;
  a[857][23] = 0;
  a[858][23] = 0;
  a[859][23] = 0;
  a[860][23] = 0;
  a[861][23] = 0;
  a[862][23] = 0;
  a[863][23] = 0;
  a[864][23] = 0;
  a[865][23] = 0;
  a[866][23] = 0;
  a[867][23] = 0;
  a[868][23] = 0;
  a[869][23] = 0;
  a[870][23] = 0;
  a[871][23] = 0;
  a[872][23] = 0;
  a[873][23] = 0;
  a[874][23] = 0;
  a[875][23] = 0;
  a[876][23] = 0;
  a[877][23] = 0;
  a[878][23] = 0;
  a[879][23] = 0;
  a[880][23] = 0;
  a[881][23] = 0;
  a[882][23] = 0;
  a[883][23] = 0;
  a[884][23] = 0;
  a[885][23] = 0;
  a[886][23] = 0;
  a[887][23] = 0;
  a[888][23] = 0;
  a[889][23] = 0;
  a[890][23] = 0;
  a[891][23] = 0;
  a[892][23] = 0;
  a[893][23] = 0;
  a[894][23] = 0;
  a[895][23] = 0;
  a[896][23] = 0;
  a[897][23] = 0;
  a[898][23] = 0;
  a[899][23] = 0;
  a[900][23] = 0;
  a[901][23] = 0;
  a[902][23] = 0;
  a[903][23] = 0;
  a[904][23] = 0;
  a[905][23] = 0;
  a[906][23] = 0;
  a[907][23] = 0;
  a[908][23] = 0;
  a[909][23] = 0;
  a[910][23] = 0;
  a[911][23] = 0;
  a[912][23] = 0;
  a[913][23] = 0;
  a[914][23] = 0;
  a[915][23] = 0;
  a[916][23] = 0;
  a[917][23] = 0;
  a[918][23] = 0;
  a[919][23] = 0;
  a[920][23] = 0;
  a[921][23] = 0;
  a[922][23] = 0;
  a[923][23] = 0;
  a[924][23] = 0;
  a[925][23] = 0;
  a[926][23] = 0;
  a[927][23] = 0;
  a[928][23] = 0;
  a[929][23] = 0;
  a[930][23] = 0;
  a[931][23] = 0;
  a[932][23] = 0;
  a[933][23] = 0;
  a[934][23] = 0;
  a[935][23] = 0;
  a[936][23] = 0;
  a[937][23] = 0;
  a[938][23] = 0;
  a[939][23] = 0;
  a[940][23] = 0;
  a[941][23] = 0;
  a[942][23] = 0;
  a[943][23] = 0;
  a[944][23] = 0;
  a[945][23] = 0;
  a[946][23] = 0;
  a[947][23] = 0;
  a[948][23] = 0;
  a[949][23] = 0;
  a[950][23] = 0;
  a[951][23] = 0;
  a[952][23] = 0;
  a[953][23] = 0;
  a[954][23] = 0;
  a[955][23] = 0;
  a[956][23] = 0;
  a[957][23] = 0;
  a[958][23] = 0;
  a[959][23] = 0;
  a[960][23] = 0;
  a[961][23] = 0;
  a[962][23] = 0;
  a[963][23] = 0;
  a[964][23] = 0;
  a[965][23] = 0;
  a[966][23] = 0;
  a[967][23] = 0;
  a[968][23] = 0;
  a[969][23] = 0;
  a[970][23] = 0;
  a[971][23] = 0;
  a[972][23] = 0;
  a[973][23] = 0;
  a[974][23] = 0;
  a[975][23] = 0;
  a[976][23] = 0;
  a[977][23] = 0;
  a[978][23] = 0;
  a[979][23] = 0;
  a[980][23] = 0;
  a[981][23] = 0;
  a[982][23] = 0;
  a[983][23] = 0;
  a[984][23] = 0;
  a[985][23] = 0;
  a[986][23] = 0;
  a[987][23] = 0;
  a[988][23] = 0;
  a[989][23] = 0;
  a[990][23] = 0;
  a[991][23] = 0;
  a[992][23] = 0;
  a[993][23] = 0;
  a[994][23] = 0;
  a[995][23] = 0;
  a[996][23] = 0;
  a[997][23] = 0;
  a[998][23] = 0;
  a[999][23] = 0;
  a[1000][23] = 0;
  a[800][24] = 863522038;
  a[801][24] = 0;
  a[802][24] = 0;
  a[803][24] = 0;
  a[804][24] = 0;
  a[805][24] = 0;
  a[806][24] = 0;
  a[807][24] = 0;
  a[808][24] = 0;
  a[809][24] = 0;
  a[810][24] = 0;
  a[811][24] = 0;
  a[812][24] = 0;
  a[813][24] = 0;
  a[814][24] = 0;
  a[815][24] = 0;
  a[816][24] = 0;
  a[817][24] = 0;
  a[818][24] = 0;
  a[819][24] = 0;
  a[820][24] = 0;
  a[821][24] = 0;
  a[822][24] = 0;
  a[823][24] = 0;
  a[824][24] = 0;
  a[825][24] = 0;
  a[826][24] = 0;
  a[827][24] = 0;
  a[828][24] = 0;
  a[829][24] = 0;
  a[830][24] = 0;
  a[831][24] = 0;
  a[832][24] = 0;
  a[833][24] = 0;
  a[834][24] = 0;
  a[835][24] = 0;
  a[836][24] = 0;
  a[837][24] = 0;
  a[838][24] = 0;
  a[839][24] = 0;
  a[840][24] = 0;
  a[841][24] = 0;
  a[842][24] = 0;
  a[843][24] = 0;
  a[844][24] = 0;
  a[845][24] = 0;
  a[846][24] = 0;
  a[847][24] = 0;
  a[848][24] = 0;
  a[849][24] = 0;
  a[850][24] = 0;
  a[851][24] = 0;
  a[852][24] = 0;
  a[853][24] = 0;
  a[854][24] = 0;
  a[855][24] = 0;
  a[856][24] = 0;
  a[857][24] = 0;
  a[858][24] = 0;
  a[859][24] = 0;
  a[860][24] = 0;
  a[861][24] = 0;
  a[862][24] = 0;
  a[863][24] = 0;
  a[864][24] = 0;
  a[865][24] = 0;
  a[866][24] = 0;
  a[867][24] = 0;
  a[868][24] = 0;
  a[869][24] = 0;
  a[870][24] = 0;
  a[871][24] = 0;
  a[872][24] = 0;
  a[873][24] = 0;
  a[874][24] = 0;
  a[875][24] = 0;
  a[876][24] = 0;
  a[877][24] = 0;
  a[878][24] = 0;
  a[879][24] = 0;
  a[880][24] = 0;
  a[881][24] = 0;
  a[882][24] = 0;
  a[883][24] = 0;
  a[884][24] = 0;
  a[885][24] = 0;
  a[886][24] = 0;
  a[887][24] = 0;
  a[888][24] = 0;
  a[889][24] = 0;
  a[890][24] = 0;
  a[891][24] = 0;
  a[892][24] = 0;
  a[893][24] = 0;
  a[894][24] = 0;
  a[895][24] = 0;
  a[896][24] = 0;
  a[897][24] = 0;
  a[898][24] = 0;
  a[899][24] = 0;
  a[900][24] = 0;
  a[901][24] = 0;
  a[902][24] = 0;
  a[903][24] = 0;
  a[904][24] = 0;
  a[905][24] = 0;
  a[906][24] = 0;
  a[907][24] = 0;
  a[908][24] = 0;
  a[909][24] = 0;
  a[910][24] = 0;
  a[911][24] = 0;
  a[912][24] = 0;
  a[913][24] = 0;
  a[914][24] = 0;
  a[915][24] = 0;
  a[916][24] = 0;
  a[917][24] = 0;
  a[918][24] = 0;
  a[919][24] = 0;
  a[920][24] = 0;
  a[921][24] = 0;
  a[922][24] = 0;
  a[923][24] = 0;
  a[924][24] = 0;
  a[925][24] = 0;
  a[926][24] = 0;
  a[927][24] = 0;
  a[928][24] = 0;
  a[929][24] = 0;
  a[930][24] = 0;
  a[931][24] = 0;
  a[932][24] = 0;
  a[933][24] = 0;
  a[934][24] = 0;
  a[935][24] = 0;
  a[936][24] = 0;
  a[937][24] = 0;
  a[938][24] = 0;
  a[939][24] = 0;
  a[940][24] = 0;
  a[941][24] = 0;
  a[942][24] = 0;
  a[943][24] = 0;
  a[944][24] = 0;
  a[945][24] = 0;
  a[946][24] = 0;
  a[947][24] = 0;
  a[948][24] = 0;
  a[949][24] = 0;
  a[950][24] = 0;
  a[951][24] = 0;
  a[952][24] = 0;
  a[953][24] = 0;
  a[954][24] = 0;
  a[955][24] = 0;
  a[956][24] = 0;
  a[957][24] = 0;
  a[958][24] = 0;
  a[959][24] = 0;
  a[960][24] = 0;
  a[961][24] = 0;
  a[962][24] = 0;
  a[963][24] = 0;
  a[964][24] = 0;
  a[965][24] = 0;
  a[966][24] = 0;
  a[967][24] = 0;
  a[968][24] = 0;
  a[969][24] = 0;
  a[970][24] = 0;
  a[971][24] = 0;
  a[972][24] = 0;
  a[973][24] = 0;
  a[974][24] = 0;
  a[975][24] = 0;
  a[976][24] = 0;
  a[977][24] = 0;
  a[978][24] = 0;
  a[979][24] = 0;
  a[980][24] = 0;
  a[981][24] = 0;
  a[982][24] = 0;
  a[983][24] = 0;
  a[984][24] = 0;
  a[985][24] = 0;
  a[986][24] = 0;
  a[987][24] = 0;
  a[988][24] = 0;
  a[989][24] = 0;
  a[990][24] = 0;
  a[991][24] = 0;
  a[992][24] = 0;
  a[993][24] = 0;
  a[994][24] = 0;
  a[995][24] = 0;
  a[996][24] = 0;
  a[997][24] = 0;
  a[998][24] = 0;
  a[999][24] = 0;
  a[1000][24] = 0;
  a[800][25] = 223364203;
  a[801][25] = 0;
  a[802][25] = 0;
  a[803][25] = 0;
  a[804][25] = 0;
  a[805][25] = 0;
  a[806][25] = 0;
  a[807][25] = 0;
  a[808][25] = 0;
  a[809][25] = 0;
  a[810][25] = 0;
  a[811][25] = 0;
  a[812][25] = 0;
  a[813][25] = 0;
  a[814][25] = 0;
  a[815][25] = 0;
  a[816][25] = 0;
  a[817][25] = 0;
  a[818][25] = 0;
  a[819][25] = 0;
  a[820][25] = 0;
  a[821][25] = 0;
  a[822][25] = 0;
  a[823][25] = 0;
  a[824][25] = 0;
  a[825][25] = 0;
  a[826][25] = 0;
  a[827][25] = 0;
  a[828][25] = 0;
  a[829][25] = 0;
  a[830][25] = 0;
  a[831][25] = 0;
  a[832][25] = 0;
  a[833][25] = 0;
  a[834][25] = 0;
  a[835][25] = 0;
  a[836][25] = 0;
  a[837][25] = 0;
  a[838][25] = 0;
  a[839][25] = 0;
  a[840][25] = 0;
  a[841][25] = 0;
  a[842][25] = 0;
  a[843][25] = 0;
  a[844][25] = 0;
  a[845][25] = 0;
  a[846][25] = 0;
  a[847][25] = 0;
  a[848][25] = 0;
  a[849][25] = 0;
  a[850][25] = 0;
  a[851][25] = 0;
  a[852][25] = 0;
  a[853][25] = 0;
  a[854][25] = 0;
  a[855][25] = 0;
  a[856][25] = 0;
  a[857][25] = 0;
  a[858][25] = 0;
  a[859][25] = 0;
  a[860][25] = 0;
  a[861][25] = 0;
  a[862][25] = 0;
  a[863][25] = 0;
  a[864][25] = 0;
  a[865][25] = 0;
  a[866][25] = 0;
  a[867][25] = 0;
  a[868][25] = 0;
  a[869][25] = 0;
  a[870][25] = 0;
  a[871][25] = 0;
  a[872][25] = 0;
  a[873][25] = 0;
  a[874][25] = 0;
  a[875][25] = 0;
  a[876][25] = 0;
  a[877][25] = 0;
  a[878][25] = 0;
  a[879][25] = 0;
  a[880][25] = 0;
  a[881][25] = 0;
  a[882][25] = 0;
  a[883][25] = 0;
  a[884][25] = 0;
  a[885][25] = 0;
  a[886][25] = 0;
  a[887][25] = 0;
  a[888][25] = 0;
  a[889][25] = 0;
  a[890][25] = 0;
  a[891][25] = 0;
  a[892][25] = 0;
  a[893][25] = 0;
  a[894][25] = 0;
  a[895][25] = 0;
  a[896][25] = 0;
  a[897][25] = 0;
  a[898][25] = 0;
  a[899][25] = 0;
  a[900][25] = 0;
  a[901][25] = 0;
  a[902][25] = 0;
  a[903][25] = 0;
  a[904][25] = 0;
  a[905][25] = 0;
  a[906][25] = 0;
  a[907][25] = 0;
  a[908][25] = 0;
  a[909][25] = 0;
  a[910][25] = 0;
  a[911][25] = 0;
  a[912][25] = 0;
  a[913][25] = 0;
  a[914][25] = 0;
  a[915][25] = 0;
  a[916][25] = 0;
  a[917][25] = 0;
  a[918][25] = 0;
  a[919][25] = 0;
  a[920][25] = 0;
  a[921][25] = 0;
  a[922][25] = 0;
  a[923][25] = 0;
  a[924][25] = 0;
  a[925][25] = 0;
  a[926][25] = 0;
  a[927][25] = 0;
  a[928][25] = 0;
  a[929][25] = 0;
  a[930][25] = 0;
  a[931][25] = 0;
  a[932][25] = 0;
  a[933][25] = 0;
  a[934][25] = 0;
  a[935][25] = 0;
  a[936][25] = 0;
  a[937][25] = 0;
  a[938][25] = 0;
  a[939][25] = 0;
  a[940][25] = 0;
  a[941][25] = 0;
  a[942][25] = 0;
  a[943][25] = 0;
  a[944][25] = 0;
  a[945][25] = 0;
  a[946][25] = 0;
  a[947][25] = 0;
  a[948][25] = 0;
  a[949][25] = 0;
  a[950][25] = 0;
  a[951][25] = 0;
  a[952][25] = 0;
  a[953][25] = 0;
  a[954][25] = 0;
  a[955][25] = 0;
  a[956][25] = 0;
  a[957][25] = 0;
  a[958][25] = 0;
  a[959][25] = 0;
  a[960][25] = 0;
  a[961][25] = 0;
  a[962][25] = 0;
  a[963][25] = 0;
  a[964][25] = 0;
  a[965][25] = 0;
  a[966][25] = 0;
  a[967][25] = 0;
  a[968][25] = 0;
  a[969][25] = 0;
  a[970][25] = 0;
  a[971][25] = 0;
  a[972][25] = 0;
  a[973][25] = 0;
  a[974][25] = 0;
  a[975][25] = 0;
  a[976][25] = 0;
  a[977][25] = 0;
  a[978][25] = 0;
  a[979][25] = 0;
  a[980][25] = 0;
  a[981][25] = 0;
  a[982][25] = 0;
  a[983][25] = 0;
  a[984][25] = 0;
  a[985][25] = 0;
  a[986][25] = 0;
  a[987][25] = 0;
  a[988][25] = 0;
  a[989][25] = 0;
  a[990][25] = 0;
  a[991][25] = 0;
  a[992][25] = 0;
  a[993][25] = 0;
  a[994][25] = 0;
  a[995][25] = 0;
  a[996][25] = 0;
  a[997][25] = 0;
  a[998][25] = 0;
  a[999][25] = 0;
  a[1000][25] = 0;
  a[800][26] = 135169406;
  a[801][26] = 0;
  a[802][26] = 0;
  a[803][26] = 0;
  a[804][26] = 0;
  a[805][26] = 0;
  a[806][26] = 0;
  a[807][26] = 0;
  a[808][26] = 0;
  a[809][26] = 0;
  a[810][26] = 0;
  a[811][26] = 0;
  a[812][26] = 0;
  a[813][26] = 0;
  a[814][26] = 0;
  a[815][26] = 0;
  a[816][26] = 0;
  a[817][26] = 0;
  a[818][26] = 0;
  a[819][26] = 0;
  a[820][26] = 0;
  a[821][26] = 0;
  a[822][26] = 0;
  a[823][26] = 0;
  a[824][26] = 0;
  a[825][26] = 0;
  a[826][26] = 0;
  a[827][26] = 0;
  a[828][26] = 0;
  a[829][26] = 0;
  a[830][26] = 0;
  a[831][26] = 0;
  a[832][26] = 0;
  a[833][26] = 0;
  a[834][26] = 0;
  a[835][26] = 0;
  a[836][26] = 0;
  a[837][26] = 0;
  a[838][26] = 0;
  a[839][26] = 0;
  a[840][26] = 0;
  a[841][26] = 0;
  a[842][26] = 0;
  a[843][26] = 0;
  a[844][26] = 0;
  a[845][26] = 0;
  a[846][26] = 0;
  a[847][26] = 0;
  a[848][26] = 0;
  a[849][26] = 0;
  a[850][26] = 0;
  a[851][26] = 0;
  a[852][26] = 0;
  a[853][26] = 0;
  a[854][26] = 0;
  a[855][26] = 0;
  a[856][26] = 0;
  a[857][26] = 0;
  a[858][26] = 0;
  a[859][26] = 0;
  a[860][26] = 0;
  a[861][26] = 0;
  a[862][26] = 0;
  a[863][26] = 0;
  a[864][26] = 0;
  a[865][26] = 0;
  a[866][26] = 0;
  a[867][26] = 0;
  a[868][26] = 0;
  a[869][26] = 0;
  a[870][26] = 0;
  a[871][26] = 0;
  a[872][26] = 0;
  a[873][26] = 0;
  a[874][26] = 0;
  a[875][26] = 0;
  a[876][26] = 0;
  a[877][26] = 0;
  a[878][26] = 0;
  a[879][26] = 0;
  a[880][26] = 0;
  a[881][26] = 0;
  a[882][26] = 0;
  a[883][26] = 0;
  a[884][26] = 0;
  a[885][26] = 0;
  a[886][26] = 0;
  a[887][26] = 0;
  a[888][26] = 0;
  a[889][26] = 0;
  a[890][26] = 0;
  a[891][26] = 0;
  a[892][26] = 0;
  a[893][26] = 0;
  a[894][26] = 0;
  a[895][26] = 0;
  a[896][26] = 0;
  a[897][26] = 0;
  a[898][26] = 0;
  a[899][26] = 0;
  a[900][26] = 0;
  a[901][26] = 0;
  a[902][26] = 0;
  a[903][26] = 0;
  a[904][26] = 0;
  a[905][26] = 0;
  a[906][26] = 0;
  a[907][26] = 0;
  a[908][26] = 0;
  a[909][26] = 0;
  a[910][26] = 0;
  a[911][26] = 0;
  a[912][26] = 0;
  a[913][26] = 0;
  a[914][26] = 0;
  a[915][26] = 0;
  a[916][26] = 0;
  a[917][26] = 0;
  a[918][26] = 0;
  a[919][26] = 0;
  a[920][26] = 0;
  a[921][26] = 0;
  a[922][26] = 0;
  a[923][26] = 0;
  a[924][26] = 0;
  a[925][26] = 0;
  a[926][26] = 0;
  a[927][26] = 0;
  a[928][26] = 0;
  a[929][26] = 0;
  a[930][26] = 0;
  a[931][26] = 0;
  a[932][26] = 0;
  a[933][26] = 0;
  a[934][26] = 0;
  a[935][26] = 0;
  a[936][26] = 0;
  a[937][26] = 0;
  a[938][26] = 0;
  a[939][26] = 0;
  a[940][26] = 0;
  a[941][26] = 0;
  a[942][26] = 0;
  a[943][26] = 0;
  a[944][26] = 0;
  a[945][26] = 0;
  a[946][26] = 0;
  a[947][26] = 0;
  a[948][26] = 0;
  a[949][26] = 0;
  a[950][26] = 0;
  a[951][26] = 0;
  a[952][26] = 0;
  a[953][26] = 0;
  a[954][26] = 0;
  a[955][26] = 0;
  a[956][26] = 0;
  a[957][26] = 0;
  a[958][26] = 0;
  a[959][26] = 0;
  a[960][26] = 0;
  a[961][26] = 0;
  a[962][26] = 0;
  a[963][26] = 0;
  a[964][26] = 0;
  a[965][26] = 0;
  a[966][26] = 0;
  a[967][26] = 0;
  a[968][26] = 0;
  a[969][26] = 0;
  a[970][26] = 0;
  a[971][26] = 0;
  a[972][26] = 0;
  a[973][26] = 0;
  a[974][26] = 0;
  a[975][26] = 0;
  a[976][26] = 0;
  a[977][26] = 0;
  a[978][26] = 0;
  a[979][26] = 0;
  a[980][26] = 0;
  a[981][26] = 0;
  a[982][26] = 0;
  a[983][26] = 0;
  a[984][26] = 0;
  a[985][26] = 0;
  a[986][26] = 0;
  a[987][26] = 0;
  a[988][26] = 0;
  a[989][26] = 0;
  a[990][26] = 0;
  a[991][26] = 0;
  a[992][26] = 0;
  a[993][26] = 0;
  a[994][26] = 0;
  a[995][26] = 0;
  a[996][26] = 0;
  a[997][26] = 0;
  a[998][26] = 0;
  a[999][26] = 0;
  a[1000][26] = 0;
  a[800][27] = 276054145;
  a[801][27] = 0;
  a[802][27] = 0;
  a[803][27] = 0;
  a[804][27] = 0;
  a[805][27] = 0;
  a[806][27] = 0;
  a[807][27] = 0;
  a[808][27] = 0;
  a[809][27] = 0;
  a[810][27] = 0;
  a[811][27] = 0;
  a[812][27] = 0;
  a[813][27] = 0;
  a[814][27] = 0;
  a[815][27] = 0;
  a[816][27] = 0;
  a[817][27] = 0;
  a[818][27] = 0;
  a[819][27] = 0;
  a[820][27] = 0;
  a[821][27] = 0;
  a[822][27] = 0;
  a[823][27] = 0;
  a[824][27] = 0;
  a[825][27] = 0;
  a[826][27] = 0;
  a[827][27] = 0;
  a[828][27] = 0;
  a[829][27] = 0;
  a[830][27] = 0;
  a[831][27] = 0;
  a[832][27] = 0;
  a[833][27] = 0;
  a[834][27] = 0;
  a[835][27] = 0;
  a[836][27] = 0;
  a[837][27] = 0;
  a[838][27] = 0;
  a[839][27] = 0;
  a[840][27] = 0;
  a[841][27] = 0;
  a[842][27] = 0;
  a[843][27] = 0;
  a[844][27] = 0;
  a[845][27] = 0;
  a[846][27] = 0;
  a[847][27] = 0;
  a[848][27] = 0;
  a[849][27] = 0;
  a[850][27] = 0;
  a[851][27] = 0;
  a[852][27] = 0;
  a[853][27] = 0;
  a[854][27] = 0;
  a[855][27] = 0;
  a[856][27] = 0;
  a[857][27] = 0;
  a[858][27] = 0;
  a[859][27] = 0;
  a[860][27] = 0;
  a[861][27] = 0;
  a[862][27] = 0;
  a[863][27] = 0;
  a[864][27] = 0;
  a[865][27] = 0;
  a[866][27] = 0;
  a[867][27] = 0;
  a[868][27] = 0;
  a[869][27] = 0;
  a[870][27] = 0;
  a[871][27] = 0;
  a[872][27] = 0;
  a[873][27] = 0;
  a[874][27] = 0;
  a[875][27] = 0;
  a[876][27] = 0;
  a[877][27] = 0;
  a[878][27] = 0;
  a[879][27] = 0;
  a[880][27] = 0;
  a[881][27] = 0;
  a[882][27] = 0;
  a[883][27] = 0;
  a[884][27] = 0;
  a[885][27] = 0;
  a[886][27] = 0;
  a[887][27] = 0;
  a[888][27] = 0;
  a[889][27] = 0;
  a[890][27] = 0;
  a[891][27] = 0;
  a[892][27] = 0;
  a[893][27] = 0;
  a[894][27] = 0;
  a[895][27] = 0;
  a[896][27] = 0;
  a[897][27] = 0;
  a[898][27] = 0;
  a[899][27] = 0;
  a[900][27] = 0;
  a[901][27] = 0;
  a[902][27] = 0;
  a[903][27] = 0;
  a[904][27] = 0;
  a[905][27] = 0;
  a[906][27] = 0;
  a[907][27] = 0;
  a[908][27] = 0;
  a[909][27] = 0;
  a[910][27] = 0;
  a[911][27] = 0;
  a[912][27] = 0;
  a[913][27] = 0;
  a[914][27] = 0;
  a[915][27] = 0;
  a[916][27] = 0;
  a[917][27] = 0;
  a[918][27] = 0;
  a[919][27] = 0;
  a[920][27] = 0;
  a[921][27] = 0;
  a[922][27] = 0;
  a[923][27] = 0;
  a[924][27] = 0;
  a[925][27] = 0;
  a[926][27] = 0;
  a[927][27] = 0;
  a[928][27] = 0;
  a[929][27] = 0;
  a[930][27] = 0;
  a[931][27] = 0;
  a[932][27] = 0;
  a[933][27] = 0;
  a[934][27] = 0;
  a[935][27] = 0;
  a[936][27] = 0;
  a[937][27] = 0;
  a[938][27] = 0;
  a[939][27] = 0;
  a[940][27] = 0;
  a[941][27] = 0;
  a[942][27] = 0;
  a[943][27] = 0;
  a[944][27] = 0;
  a[945][27] = 0;
  a[946][27] = 0;
  a[947][27] = 0;
  a[948][27] = 0;
  a[949][27] = 0;
  a[950][27] = 0;
  a[951][27] = 0;
  a[952][27] = 0;
  a[953][27] = 0;
  a[954][27] = 0;
  a[955][27] = 0;
  a[956][27] = 0;
  a[957][27] = 0;
  a[958][27] = 0;
  a[959][27] = 0;
  a[960][27] = 0;
  a[961][27] = 0;
  a[962][27] = 0;
  a[963][27] = 0;
  a[964][27] = 0;
  a[965][27] = 0;
  a[966][27] = 0;
  a[967][27] = 0;
  a[968][27] = 0;
  a[969][27] = 0;
  a[970][27] = 0;
  a[971][27] = 0;
  a[972][27] = 0;
  a[973][27] = 0;
  a[974][27] = 0;
  a[975][27] = 0;
  a[976][27] = 0;
  a[977][27] = 0;
  a[978][27] = 0;
  a[979][27] = 0;
  a[980][27] = 0;
  a[981][27] = 0;
  a[982][27] = 0;
  a[983][27] = 0;
  a[984][27] = 0;
  a[985][27] = 0;
  a[986][27] = 0;
  a[987][27] = 0;
  a[988][27] = 0;
  a[989][27] = 0;
  a[990][27] = 0;
  a[991][27] = 0;
  a[992][27] = 0;
  a[993][27] = 0;
  a[994][27] = 0;
  a[995][27] = 0;
  a[996][27] = 0;
  a[997][27] = 0;
  a[998][27] = 0;
  a[999][27] = 0;
  a[1000][27] = 0;
  a[800][28] = 981336826;
  a[801][28] = 0;
  a[802][28] = 0;
  a[803][28] = 0;
  a[804][28] = 0;
  a[805][28] = 0;
  a[806][28] = 0;
  a[807][28] = 0;
  a[808][28] = 0;
  a[809][28] = 0;
  a[810][28] = 0;
  a[811][28] = 0;
  a[812][28] = 0;
  a[813][28] = 0;
  a[814][28] = 0;
  a[815][28] = 0;
  a[816][28] = 0;
  a[817][28] = 0;
  a[818][28] = 0;
  a[819][28] = 0;
  a[820][28] = 0;
  a[821][28] = 0;
  a[822][28] = 0;
  a[823][28] = 0;
  a[824][28] = 0;
  a[825][28] = 0;
  a[826][28] = 0;
  a[827][28] = 0;
  a[828][28] = 0;
  a[829][28] = 0;
  a[830][28] = 0;
  a[831][28] = 0;
  a[832][28] = 0;
  a[833][28] = 0;
  a[834][28] = 0;
  a[835][28] = 0;
  a[836][28] = 0;
  a[837][28] = 0;
  a[838][28] = 0;
  a[839][28] = 0;
  a[840][28] = 0;
  a[841][28] = 0;
  a[842][28] = 0;
  a[843][28] = 0;
  a[844][28] = 0;
  a[845][28] = 0;
  a[846][28] = 0;
  a[847][28] = 0;
  a[848][28] = 0;
  a[849][28] = 0;
  a[850][28] = 0;
  a[851][28] = 0;
  a[852][28] = 0;
  a[853][28] = 0;
  a[854][28] = 0;
  a[855][28] = 0;
  a[856][28] = 0;
  a[857][28] = 0;
  a[858][28] = 0;
  a[859][28] = 0;
  a[860][28] = 0;
  a[861][28] = 0;
  a[862][28] = 0;
  a[863][28] = 0;
  a[864][28] = 0;
  a[865][28] = 0;
  a[866][28] = 0;
  a[867][28] = 0;
  a[868][28] = 0;
  a[869][28] = 0;
  a[870][28] = 0;
  a[871][28] = 0;
  a[872][28] = 0;
  a[873][28] = 0;
  a[874][28] = 0;
  a[875][28] = 0;
  a[876][28] = 0;
  a[877][28] = 0;
  a[878][28] = 0;
  a[879][28] = 0;
  a[880][28] = 0;
  a[881][28] = 0;
  a[882][28] = 0;
  a[883][28] = 0;
  a[884][28] = 0;
  a[885][28] = 0;
  a[886][28] = 0;
  a[887][28] = 0;
  a[888][28] = 0;
  a[889][28] = 0;
  a[890][28] = 0;
  a[891][28] = 0;
  a[892][28] = 0;
  a[893][28] = 0;
  a[894][28] = 0;
  a[895][28] = 0;
  a[896][28] = 0;
  a[897][28] = 0;
  a[898][28] = 0;
  a[899][28] = 0;
  a[900][28] = 0;
  a[901][28] = 0;
  a[902][28] = 0;
  a[903][28] = 0;
  a[904][28] = 0;
  a[905][28] = 0;
  a[906][28] = 0;
  a[907][28] = 0;
  a[908][28] = 0;
  a[909][28] = 0;
  a[910][28] = 0;
  a[911][28] = 0;
  a[912][28] = 0;
  a[913][28] = 0;
  a[914][28] = 0;
  a[915][28] = 0;
  a[916][28] = 0;
  a[917][28] = 0;
  a[918][28] = 0;
  a[919][28] = 0;
  a[920][28] = 0;
  a[921][28] = 0;
  a[922][28] = 0;
  a[923][28] = 0;
  a[924][28] = 0;
  a[925][28] = 0;
  a[926][28] = 0;
  a[927][28] = 0;
  a[928][28] = 0;
  a[929][28] = 0;
  a[930][28] = 0;
  a[931][28] = 0;
  a[932][28] = 0;
  a[933][28] = 0;
  a[934][28] = 0;
  a[935][28] = 0;
  a[936][28] = 0;
  a[937][28] = 0;
  a[938][28] = 0;
  a[939][28] = 0;
  a[940][28] = 0;
  a[941][28] = 0;
  a[942][28] = 0;
  a[943][28] = 0;
  a[944][28] = 0;
  a[945][28] = 0;
  a[946][28] = 0;
  a[947][28] = 0;
  a[948][28] = 0;
  a[949][28] = 0;
  a[950][28] = 0;
  a[951][28] = 0;
  a[952][28] = 0;
  a[953][28] = 0;
  a[954][28] = 0;
  a[955][28] = 0;
  a[956][28] = 0;
  a[957][28] = 0;
  a[958][28] = 0;
  a[959][28] = 0;
  a[960][28] = 0;
  a[961][28] = 0;
  a[962][28] = 0;
  a[963][28] = 0;
  a[964][28] = 0;
  a[965][28] = 0;
  a[966][28] = 0;
  a[967][28] = 0;
  a[968][28] = 0;
  a[969][28] = 0;
  a[970][28] = 0;
  a[971][28] = 0;
  a[972][28] = 0;
  a[973][28] = 0;
  a[974][28] = 0;
  a[975][28] = 0;
  a[976][28] = 0;
  a[977][28] = 0;
  a[978][28] = 0;
  a[979][28] = 0;
  a[980][28] = 0;
  a[981][28] = 0;
  a[982][28] = 0;
  a[983][28] = 0;
  a[984][28] = 0;
  a[985][28] = 0;
  a[986][28] = 0;
  a[987][28] = 0;
  a[988][28] = 0;
  a[989][28] = 0;
  a[990][28] = 0;
  a[991][28] = 0;
  a[992][28] = 0;
  a[993][28] = 0;
  a[994][28] = 0;
  a[995][28] = 0;
  a[996][28] = 0;
  a[997][28] = 0;
  a[998][28] = 0;
  a[999][28] = 0;
  a[1000][28] = 0;
  a[800][29] = 21504211;
  a[801][29] = 0;
  a[802][29] = 0;
  a[803][29] = 0;
  a[804][29] = 0;
  a[805][29] = 0;
  a[806][29] = 0;
  a[807][29] = 0;
  a[808][29] = 0;
  a[809][29] = 0;
  a[810][29] = 0;
  a[811][29] = 0;
  a[812][29] = 0;
  a[813][29] = 0;
  a[814][29] = 0;
  a[815][29] = 0;
  a[816][29] = 0;
  a[817][29] = 0;
  a[818][29] = 0;
  a[819][29] = 0;
  a[820][29] = 0;
  a[821][29] = 0;
  a[822][29] = 0;
  a[823][29] = 0;
  a[824][29] = 0;
  a[825][29] = 0;
  a[826][29] = 0;
  a[827][29] = 0;
  a[828][29] = 0;
  a[829][29] = 0;
  a[830][29] = 0;
  a[831][29] = 0;
  a[832][29] = 0;
  a[833][29] = 0;
  a[834][29] = 0;
  a[835][29] = 0;
  a[836][29] = 0;
  a[837][29] = 0;
  a[838][29] = 0;
  a[839][29] = 0;
  a[840][29] = 0;
  a[841][29] = 0;
  a[842][29] = 0;
  a[843][29] = 0;
  a[844][29] = 0;
  a[845][29] = 0;
  a[846][29] = 0;
  a[847][29] = 0;
  a[848][29] = 0;
  a[849][29] = 0;
  a[850][29] = 0;
  a[851][29] = 0;
  a[852][29] = 0;
  a[853][29] = 0;
  a[854][29] = 0;
  a[855][29] = 0;
  a[856][29] = 0;
  a[857][29] = 0;
  a[858][29] = 0;
  a[859][29] = 0;
  a[860][29] = 0;
  a[861][29] = 0;
  a[862][29] = 0;
  a[863][29] = 0;
  a[864][29] = 0;
  a[865][29] = 0;
  a[866][29] = 0;
  a[867][29] = 0;
  a[868][29] = 0;
  a[869][29] = 0;
  a[870][29] = 0;
  a[871][29] = 0;
  a[872][29] = 0;
  a[873][29] = 0;
  a[874][29] = 0;
  a[875][29] = 0;
  a[876][29] = 0;
  a[877][29] = 0;
  a[878][29] = 0;
  a[879][29] = 0;
  a[880][29] = 0;
  a[881][29] = 0;
  a[882][29] = 0;
  a[883][29] = 0;
  a[884][29] = 0;
  a[885][29] = 0;
  a[886][29] = 0;
  a[887][29] = 0;
  a[888][29] = 0;
  a[889][29] = 0;
  a[890][29] = 0;
  a[891][29] = 0;
  a[892][29] = 0;
  a[893][29] = 0;
  a[894][29] = 0;
  a[895][29] = 0;
  a[896][29] = 0;
  a[897][29] = 0;
  a[898][29] = 0;
  a[899][29] = 0;
  a[900][29] = 0;
  a[901][29] = 0;
  a[902][29] = 0;
  a[903][29] = 0;
  a[904][29] = 0;
  a[905][29] = 0;
  a[906][29] = 0;
  a[907][29] = 0;
  a[908][29] = 0;
  a[909][29] = 0;
  a[910][29] = 0;
  a[911][29] = 0;
  a[912][29] = 0;
  a[913][29] = 0;
  a[914][29] = 0;
  a[915][29] = 0;
  a[916][29] = 0;
  a[917][29] = 0;
  a[918][29] = 0;
  a[919][29] = 0;
  a[920][29] = 0;
  a[921][29] = 0;
  a[922][29] = 0;
  a[923][29] = 0;
  a[924][29] = 0;
  a[925][29] = 0;
  a[926][29] = 0;
  a[927][29] = 0;
  a[928][29] = 0;
  a[929][29] = 0;
  a[930][29] = 0;
  a[931][29] = 0;
  a[932][29] = 0;
  a[933][29] = 0;
  a[934][29] = 0;
  a[935][29] = 0;
  a[936][29] = 0;
  a[937][29] = 0;
  a[938][29] = 0;
  a[939][29] = 0;
  a[940][29] = 0;
  a[941][29] = 0;
  a[942][29] = 0;
  a[943][29] = 0;
  a[944][29] = 0;
  a[945][29] = 0;
  a[946][29] = 0;
  a[947][29] = 0;
  a[948][29] = 0;
  a[949][29] = 0;
  a[950][29] = 0;
  a[951][29] = 0;
  a[952][29] = 0;
  a[953][29] = 0;
  a[954][29] = 0;
  a[955][29] = 0;
  a[956][29] = 0;
  a[957][29] = 0;
  a[958][29] = 0;
  a[959][29] = 0;
  a[960][29] = 0;
  a[961][29] = 0;
  a[962][29] = 0;
  a[963][29] = 0;
  a[964][29] = 0;
  a[965][29] = 0;
  a[966][29] = 0;
  a[967][29] = 0;
  a[968][29] = 0;
  a[969][29] = 0;
  a[970][29] = 0;
  a[971][29] = 0;
  a[972][29] = 0;
  a[973][29] = 0;
  a[974][29] = 0;
  a[975][29] = 0;
  a[976][29] = 0;
  a[977][29] = 0;
  a[978][29] = 0;
  a[979][29] = 0;
  a[980][29] = 0;
  a[981][29] = 0;
  a[982][29] = 0;
  a[983][29] = 0;
  a[984][29] = 0;
  a[985][29] = 0;
  a[986][29] = 0;
  a[987][29] = 0;
  a[988][29] = 0;
  a[989][29] = 0;
  a[990][29] = 0;
  a[991][29] = 0;
  a[992][29] = 0;
  a[993][29] = 0;
  a[994][29] = 0;
  a[995][29] = 0;
  a[996][29] = 0;
  a[997][29] = 0;
  a[998][29] = 0;
  a[999][29] = 0;
  a[1000][29] = 0;
  a[800][30] = 352119519;
  a[801][30] = 0;
  a[802][30] = 0;
  a[803][30] = 0;
  a[804][30] = 0;
  a[805][30] = 0;
  a[806][30] = 0;
  a[807][30] = 0;
  a[808][30] = 0;
  a[809][30] = 0;
  a[810][30] = 0;
  a[811][30] = 0;
  a[812][30] = 0;
  a[813][30] = 0;
  a[814][30] = 0;
  a[815][30] = 0;
  a[816][30] = 0;
  a[817][30] = 0;
  a[818][30] = 0;
  a[819][30] = 0;
  a[820][30] = 0;
  a[821][30] = 0;
  a[822][30] = 0;
  a[823][30] = 0;
  a[824][30] = 0;
  a[825][30] = 0;
  a[826][30] = 0;
  a[827][30] = 0;
  a[828][30] = 0;
  a[829][30] = 0;
  a[830][30] = 0;
  a[831][30] = 0;
  a[832][30] = 0;
  a[833][30] = 0;
  a[834][30] = 0;
  a[835][30] = 0;
  a[836][30] = 0;
  a[837][30] = 0;
  a[838][30] = 0;
  a[839][30] = 0;
  a[840][30] = 0;
  a[841][30] = 0;
  a[842][30] = 0;
  a[843][30] = 0;
  a[844][30] = 0;
  a[845][30] = 0;
  a[846][30] = 0;
  a[847][30] = 0;
  a[848][30] = 0;
  a[849][30] = 0;
  a[850][30] = 0;
  a[851][30] = 0;
  a[852][30] = 0;
  a[853][30] = 0;
  a[854][30] = 0;
  a[855][30] = 0;
  a[856][30] = 0;
  a[857][30] = 0;
  a[858][30] = 0;
  a[859][30] = 0;
  a[860][30] = 0;
  a[861][30] = 0;
  a[862][30] = 0;
  a[863][30] = 0;
  a[864][30] = 0;
  a[865][30] = 0;
  a[866][30] = 0;
  a[867][30] = 0;
  a[868][30] = 0;
  a[869][30] = 0;
  a[870][30] = 0;
  a[871][30] = 0;
  a[872][30] = 0;
  a[873][30] = 0;
  a[874][30] = 0;
  a[875][30] = 0;
  a[876][30] = 0;
  a[877][30] = 0;
  a[878][30] = 0;
  a[879][30] = 0;
  a[880][30] = 0;
  a[881][30] = 0;
  a[882][30] = 0;
  a[883][30] = 0;
  a[884][30] = 0;
  a[885][30] = 0;
  a[886][30] = 0;
  a[887][30] = 0;
  a[888][30] = 0;
  a[889][30] = 0;
  a[890][30] = 0;
  a[891][30] = 0;
  a[892][30] = 0;
  a[893][30] = 0;
  a[894][30] = 0;
  a[895][30] = 0;
  a[896][30] = 0;
  a[897][30] = 0;
  a[898][30] = 0;
  a[899][30] = 0;
  a[900][30] = 0;
  a[901][30] = 0;
  a[902][30] = 0;
  a[903][30] = 0;
  a[904][30] = 0;
  a[905][30] = 0;
  a[906][30] = 0;
  a[907][30] = 0;
  a[908][30] = 0;
  a[909][30] = 0;
  a[910][30] = 0;
  a[911][30] = 0;
  a[912][30] = 0;
  a[913][30] = 0;
  a[914][30] = 0;
  a[915][30] = 0;
  a[916][30] = 0;
  a[917][30] = 0;
  a[918][30] = 0;
  a[919][30] = 0;
  a[920][30] = 0;
  a[921][30] = 0;
  a[922][30] = 0;
  a[923][30] = 0;
  a[924][30] = 0;
  a[925][30] = 0;
  a[926][30] = 0;
  a[927][30] = 0;
  a[928][30] = 0;
  a[929][30] = 0;
  a[930][30] = 0;
  a[931][30] = 0;
  a[932][30] = 0;
  a[933][30] = 0;
  a[934][30] = 0;
  a[935][30] = 0;
  a[936][30] = 0;
  a[937][30] = 0;
  a[938][30] = 0;
  a[939][30] = 0;
  a[940][30] = 0;
  a[941][30] = 0;
  a[942][30] = 0;
  a[943][30] = 0;
  a[944][30] = 0;
  a[945][30] = 0;
  a[946][30] = 0;
  a[947][30] = 0;
  a[948][30] = 0;
  a[949][30] = 0;
  a[950][30] = 0;
  a[951][30] = 0;
  a[952][30] = 0;
  a[953][30] = 0;
  a[954][30] = 0;
  a[955][30] = 0;
  a[956][30] = 0;
  a[957][30] = 0;
  a[958][30] = 0;
  a[959][30] = 0;
  a[960][30] = 0;
  a[961][30] = 0;
  a[962][30] = 0;
  a[963][30] = 0;
  a[964][30] = 0;
  a[965][30] = 0;
  a[966][30] = 0;
  a[967][30] = 0;
  a[968][30] = 0;
  a[969][30] = 0;
  a[970][30] = 0;
  a[971][30] = 0;
  a[972][30] = 0;
  a[973][30] = 0;
  a[974][30] = 0;
  a[975][30] = 0;
  a[976][30] = 0;
  a[977][30] = 0;
  a[978][30] = 0;
  a[979][30] = 0;
  a[980][30] = 0;
  a[981][30] = 0;
  a[982][30] = 0;
  a[983][30] = 0;
  a[984][30] = 0;
  a[985][30] = 0;
  a[986][30] = 0;
  a[987][30] = 0;
  a[988][30] = 0;
  a[989][30] = 0;
  a[990][30] = 0;
  a[991][30] = 0;
  a[992][30] = 0;
  a[993][30] = 0;
  a[994][30] = 0;
  a[995][30] = 0;
  a[996][30] = 0;
  a[997][30] = 0;
  a[998][30] = 0;
  a[999][30] = 0;
  a[1000][30] = 0;
}
int main() {
  prepare();
  int i, j, u, v, w, o, x, y, z, ad;
  rdi(n), rdi(h);
  if (a[n][h]) {
    print(a[n][h]);
    return 0;
  }
  dp[0][2][2][2][1] = 1;
  for (i = 1; i < n; ++i) {
    for (x = 2; x < h + 2; ++x) {
      for (y = x; y < h + 2; ++y) {
        for (z = y; z < h + 2; ++z) {
          for (o = 0; o < 2; ++o) {
            ad = dp[i - 1][x][y][z][o];
            if (!ad) continue;
            u = x > h ? x : x + 1;
            v = y > h ? y : y + 1;
            w = z > h ? z : z + 1;
            add(dp[i][u][v][w][o], ad);
            if (o) {
              add(dp[i][2][v][w][x <= h], ad);
              add(dp[i][2][u][w][y <= h], ad);
              add(dp[i][2][u][v][z <= h], ad);
            } else {
              add(dp[i][v][w][h + 1][x <= h], ad);
              add(dp[i][u][w][h + 1][y <= h], ad);
              add(dp[i][u][v][h + 1][z <= h], ad);
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (x = 0; x < h + 2; ++x)
    for (y = 0; y < h + 2; ++y)
      for (z = 0; z < h + 2; ++z)
        for (o = 0; o < 2; ++o)
          if (x <= h or y <= h or z <= h or o) add(ans, dp[n - 1][x][y][z][o]);
  ans = (long long)(ans * 4ll) % md;
  print(ans);
}

```