//#pragma GCC optimize ("-O3") #include using namespace std; //@起動時 struct initon { initon() { cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); srand((unsigned) clock() + (unsigned) time(NULL)); }; } __initon; //衝突対策 #define ws ___ws struct T { int f, s, t; T() { f = -1, s = -1, t = -1; } T(int f, int s, int t) : f(f), s(s), t(t) {} bool operator<(const T &r) const { return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 大きい順 } bool operator>(const T &r) const { return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順 } bool operator==(const T &r) const { return f == r.f && s == r.s && t == r.t; } bool operator!=(const T &r) const { return f != r.f || s != r.s || t != r.t; } int operator[](int i) { assert(i < 3); return i == 0 ? f : i == 1 ? s : t; } }; #define int long long #define ll long long #define double long double #define ull unsigned long long using dou = double; using itn = int; using str = string; using bo= bool; #define au auto using P = pair; #define fi first #define se second #define vec vector #define beg begin #define rbeg rbegin #define con continue #define bre break #define brk break #define is == //マクロ省略系コンテナ using vi = vector; #define _overloadvvi(_1, _2, _3, _4, name, ...) name #define vvi0() vec #define vvi1(a) vec a #define vvi2(a, b) vec a(b) #define vvi3(a, b, c) vec a(b,vi(c)) #define vvi4(a, b, c, d) vec a(b,vi(c,d)) #define vvi(...) _overloadvvi(__VA_ARGS__,vvi4,vvi3,vvi2 ,vvi1,vvi0)(__VA_ARGS__) using vl = vector; #define _overloadvvl(_1, _2, _3, _4, name, ...) name #define vvl1(a) vec a #define vvl2(a, b) vec a(b) #define vvl3(a, b, c) vec a(b,vl(c)) #define vvl4(a, b, c, d) vec a(b,vl(c,d)) #define vvl(...) _overloadvvl(__VA_ARGS__,vvl4,vvl3,vvl2 ,vvl1)(__VA_ARGS__) using vb = vector; #define _overloadvvb(_1, _2, _3, _4, name, ...) name #define vvb1(a) vec a #define vvb2(a, b) vec a(b) #define vvb3(a, b, c) vec a(b,vb(c)) #define vvb4(a, b, c, d) vec a(b,vb(c,d)) #define vvb(...) _overloadvvb(__VA_ARGS__,vvb4,vvb3,vvb2 ,vvb1)(__VA_ARGS__) using vs = vector; #define _overloadvvs(_1, _2, _3, _4, name, ...) name #define vvs1(a) vec a #define vvs2(a, b) vec a(b) #define vvs3(a, b, c) vec a(b,vs(c)) #define vvs4(a, b, c, d) vec a(b,vs(c,d)) #define vvs(...) _overloadvvs(__VA_ARGS__,vvs4,vvs3,vvs2 ,vvs1)(__VA_ARGS__) using vd = vector; #define _overloadvvd(_1, _2, _3, _4, name, ...) name #define vvd1(a) vec a #define vvd2(a, b) vec a(b) #define vvd3(a, b, c) vec a(b,vd(c)) #define vvd4(a, b, c, d) vec a(b,vd(c,d)) #define vvd(...) _overloadvvd(__VA_ARGS__,vvd4,vvd3,vvd2 ,vvd1)(__VA_ARGS__) using vc=vector; #define _overloadvvc(_1, _2, _3, _4, name, ...) name #define vvc1(a) vec a #define vvc2(a, b) vec a(b) #define vvc3(a, b, c) vec a(b,vc(c)) #define vvc4(a, b, c, d) vec a(b,vc(c,d)) #define vvc(...) _overloadvvc(__VA_ARGS__,vvc4,vvc3,vvc2 ,vvc1)(__VA_ARGS__) using vp = vector

; #define _overloadvvp(_1, _2, _3, _4, name, ...) name #define vvp1(a) vec a #define vvp2(a, b) vec a(b) #define vvp3(a, b, c) vec a(b,vp(c)) #define vvp4(a, b, c, d) vec a(b,vp(c,d)) using vt = vector; #define _overloadvvt(_1, _2, _3, _4, name, ...) name #define vvt1(a) vec a #define vvt2(a, b) vec a(b) #define vvt3(a, b, c) vec a(b,vt(c)) #define vvt4(a, b, c, d) vec a(b,vt(c,d)) #define v3i(a, b, c, d) vector> a(b, vector(c, vi(d))) #define v3d(a, b, c, d) vector> a(b, vector(c, vd(d))) #define v3m(a, b, c, d) vector> a(b, vector(c, vm(d))) #define _vvi vector #define _vvl vector #define _vvb vector #define _vvs vector #define _vvd vector #define _vvc vector #define _vvp vector #define PQ priority_queue, greater > #define tos to_string using mapi = map; using mapd = map; using mapc = map; using maps = map; using seti = set; using setd = set; using setc = set; using sets = set; using qui = queue; #define bset bitset #define uset unordered_set #define mset multiset #define umap unordered_map #define umapi unordered_map #define umapp unordered_map #define mmap multimap //マクロ繰り返し #define _overloadrep(_1, _2, _3, _4, name, ...) name # define _rep(i, n) for(int i = 0,_lim=n; i < _lim ; i++) #define repi(i, m, n) for(int i = m,_lim=n; i < _lim ; i++) #define repadd(i, m, n, ad) for(int i = m,_lim=n; i < _lim ; i+= ad) #define rep(...) _overloadrep(__VA_ARGS__,repadd,repi,_rep,)(__VA_ARGS__) #define _rer(i, n) for(int i = n; i >= 0 ; i--) #define reri(i, m, n) for(int i = m,_lim=n; i >= _lim ; i--) #define rerdec(i, m, n, dec) for(int i = m,_lim=n; i >= _lim ; i-=dec) #define rer(...) _overloadrep(__VA_ARGS__,rerdec,reri,_rer,)(__VA_ARGS__) #define fora(a, b) for(auto&& a : b) #define forg(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); gi++) #define fort(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); gi++)if(t!=p) //#define fort(gi, ve) for (int gi = 0, f, t, c;gi::min(); ll mi = numeric_limits::max(); const int y4[] = {-1, 1, 0, 0}; const int x4[] = {0, 0, -1, 1}; const int y8[] = {0, 1, 0, -1, -1, 1, 1, -1}; const int x8[] = {1, 0, -1, 0, 1, -1, 1, -1}; //マクロ省略形関数等 #define arsz(a) (sizeof(a)/sizeof(a[0])) #define sz(a) ((int)(a).size()) #define rs resize #define mp make_pair #define pb push_back #define pf push_front #define eb emplace_back #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() inline void sort(string &a) { sort(a.begin(), a.end()); } template inline void sort(vector &a) { sort(a.begin(), a.end()); }; template inline void sort(vector &a, int len) { sort(a.begin(), a.begin() + len); }; template inline void sort(vector &a, F f) { sort(a.begin(), a.end(), [&](T l, T r) { return f(l) < f(r); }); }; enum ___pcomparator { fisi, fisd, fdsi, fdsd, sifi, sifd, sdfi, sdfd }; inline void sort(vector

(__VA_ARGS__) template struct Matrix{ int h,w; vector a; Matrix(int n_=0):h(n_),w(n_),a(n_*n_){} Matrix(int n_, int m_):h(n_),w(m_),a(n_*m_){} Matrix(int n_, int m_, vector a_):h(n_),w(m_),a(a_){} T& get(int r,int c){return a[r*w+c];} T get(int r,int c)const{return a[r*w+c];} Matrix& operator+=(const Matrix& m) { assert(h == m.h && w == m.w); for (int i = 0; i < w*h; ++i)a[i] += m.a[i]; } Matrix& operator-=(const Matrix& m) { assert(h == m.h && w == m.w); for (int i = 0; i < w*h; ++i)a[i] -= m.a[i]; } Matrix& operator*=(const Matrix& m) { assert(w == m.h); Matrix ret(h, m.w); for (int i = 0; i < h; ++i) { for (int j = 0; j < m.w; ++j) { for (int k = 0; k < w; ++k) { ret.a[i * m.w + j] += a[i * w + k] * m.a[k * m.w + j]%MOD; } ret.a[i * m.w + j] %= MOD; } } return (*this) = ret; } Matrix operator+(const Matrix& m) const { return Matrix(*this) += m; } Matrix operator-(const Matrix& m) const { return Matrix(*this) -= m; } Matrix operator*(const Matrix& m) const { return Matrix(*this) *= m; } }; template Matrix unit(int n){ Matrix ret(n); rep(i,n)ret.get(i,i)=1; return ret; } template Matrix matpow(Matrix a,ll n){ assert(a.h==a.w); Matrix ret=unit(a.h); while(n){ if(n&1)ret*=a; a*=a; n>>=1; } return ret; } signed main(){ ll n,m; cin>>n>>m; Matrix a(m*m*m); rep(i,m)rep(j,m)rep(k,m){ int cur=i*m*m+j*m+k; int nxt1=i*m*m+j*m+(k+1)%m; int nxt2=i*m*m+(j+k)%m*m+k; int nxt3=(i+j)%m*m*m+j*m+k; a.get(nxt1,cur)+=1; a.get(nxt2,cur)+=1; a.get(nxt3,cur)+=1; } auto ret=matpow(a,n); ll ans=0; rep(i,m*m){ ans+=ret.get(0,i); } cout<