#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define int long long #define double long double typedef vector VI; typedef pair pii; typedef vector VP; typedef vector VS; typedef priority_queue PQ; templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #define fore(i,a) for(auto &i:a) #define REP(i,n) for(int i=0;i, greater > q2; ll comb(ll N_, ll C_) { const int NUM_ = 3000001; static ll fact[3000002], factr[3000002], inv[3000002]; if (fact[0] == 0) { inv[1] = fact[0] = factr[0] = 1; for (int i = 2; i <= NUM_; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod; for (int i = 1; i <= NUM_; ++i) fact[i] = fact[i - 1] * i%mod, factr[i] = factr[i - 1] * inv[i] % mod; } if (C_<0 || C_>N_) return 0; return factr[C_] * fact[N_] % mod*factr[N_ - C_] % mod; } ll modpow(ll a, ll n = mod - 2) { ll r = 1; while (n) r = r * ((n % 2) ? a : 1) % mod, a = a * a%mod, n >>= 1; return r; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; int n = M / N; int k = M % N; int ans = modpow(2, n); ans *= comb(n + k - 1, k); cout << (ans + 1 ) % mod << endl; return 0; }