#include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i=0; i--) #include namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else using u128 = unsigned __int128; u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia namespace nachia{ template struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector mods; std::vector dynmods; std::vector> table_coeff; std::vector table_coeffinv; void precalc(std::vector new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i(nmods, 1)); for(int j=0; j& x){ int nmods = mods.size(); std::vector table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j calc(std::vector> x){ int n = x[0].size(), m = x.size(); std::vector res(n); std::vector buf(m); for(int i=0; i using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 N, M; cin >> N >> M; map> T; i64 cycleTime = 1; rep(i,N) cycleTime *= 12; i64 cycleTime3 = 1; rep(i,N) cycleTime3 *= 3; i64 cycleTime4 = 1; rep(i,N) cycleTime4 *= 4; i64 cycleTime6 = 1; rep(i,N) cycleTime6 *= 6; auto garner = nachia::GarnerMod(); garner.precalc({ (unsigned int)cycleTime3, (unsigned int)cycleTime4 }); rep(i,1<<30){ i64 t = i; vector dig; rep(n,N){ dig.push_back(t%3); t /= 3; } if(t) break; reverse(dig.begin(), dig.end()); i64 t3 = 0; for(i64 a : dig) t3 = t3 * 3 + a; i64 t4 = 0; for(i64 a : dig) t4 = t4 * 4 + a; i64 t6 = 0; for(i64 a : dig) t6 = t6 * 6 + a; i64 t12 = garner.calc({ (unsigned int)t3, (unsigned int)t4 }); i64 sl = (t12 + cycleTime6 - t6) % cycleTime6; T[sl].push_back(t12); } i64 ans = 0; for(auto& f : T){ auto t = f.second; sort(t.begin(), t.end()); t.push_back(t.front() + cycleTime); rep(i,t.size()-1) if(t[i+1] - t[i] >= M+1) ans += 1; } cout << ans << endl; return 0; }