#line 1 "lib/template.hpp" #ifdef TEMPLATE #else #define TEMPLATE # pragma GCC optimize("O3") using namespace std; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using i128=__int128; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define rall(x) x.rbegin(),x.rend() #define mp make_pair #define pb push_back #define fi first #define se second #define is insert #define bg begin() #define ed end() #define all(x) x.begin(),x.end() void scan(int&a) { cin >> a; } void scan(ll&a) { cin >> a; } void scan(string&a) { cin >> a; } void scan(char&a) { cin >> a; } void scan(uint&a) { cin >> a; } void scan(ull&a) { cin >> a; } void scan(bool&a) { cin >> a; } void scan(ld&a){ cin>> a;} template void scan(vector&a) { for(auto&x:a) scan(x); } void read() {} template void read(Head&head, Tail&... tail) { scan(head); read(tail...); } #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define VC(type, name, ...) vector name(__VA_ARGS__); read(name); #define VVC(type, name, size, ...) vector> name(size, vector(__VA_ARGS__)); read(name); templatevoid print(T a) { cout << a; } template void print(vectora) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout< void PRT(T a) { print(a); cout < void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; } template bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template bool chmax(T &x, F y){ if(x T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template T ceil(T x, T y) { return floor(x + y - 1, y); } template T bmod(T x, T y) { return x - y * floor(x, y); } template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } void YesNo(bool b){ cout<<(b?"Yes":"No")<stovi(const string&s,const string&S){ vcv(s.size()); rep(i,s.size()){ auto t=S.find(s[i]); assert(t!=string::npos); v[i]=t; } return v; } template T isqrt(T x){ T F=sqrtl(x); while((F+1)*(F+1)<=x)F++; while(F*F>x)F--; return F; } template vvctrans(const vvc&a){ assert(a.size()&&a[0].size()); vvcb(a[0].size(),vc(a.size())); rep(i,a.size())rep(j,a[0].size()){ b[j][i]=a[i][j]; } return b; } template vctrans(const vc&a){ assert(a.size()&&a[0].size()); vcb(a[0].size(),string(a.size(),0)); rep(i,a.size())rep(j,a[0].size()){ b[j][i]=a[i][j]; } return b; } template int popcount(T n){ return __builtin_popcountll(n); } template L sum(vc&a){ return accumulate(all(a),L(0)); } template vcsubset(T S){ vcans; for(T x=S;x>0;x=(x-1)&S)ans.pb(x); ans.pb(0); return ans; } template T max(vc&a){ return *max_element(all(a)); } template T min(vc&a){ return *min_element(all(a)); } #ifndef COMPRESSER_STRUCT #define COMPRESSER_STRUCT template struct Compresser{ vcx; Compresser(int n=0){x.reserve(n);} Compresser(const vc&xs){ x=xs; } void push(T p){built=false;x.pb(p);} bool built=false; void build(){ if(!chmax(built,1))return; sort(all(x)); x.erase(unique(all(x)),x.end()); } int find(T v){ build(); auto itr=lower_bound(all(x),v)-x.begin(); if(itr==x.size()||x[itr]!=v)return -1; return itr; } int find_next(T v){ build(); return lower_bound(all(x),v)-x.begin(); } int size(){ build(); return x.size(); } T operator[](int i)const{ assert(0<=i&&i vc presum(vc &a){ vc ret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc &operator+=(vc &a,F b){ for (auto&v:a)v += b; return a; } template vc &operator-=(vc&a,F b){ for (auto&v:a)v-=b; return a; } template vc &operator*=(vc&a,F b){ for (auto&v:a)v*=b; return a; } template constexpr T POW(T a,T b){ T res=1; while(b){ if(b&1)res*=a; a*=a; b/=2; } return res; } constexpr ll ten(ll a){ return POW(10,a); } templateconstexpr T inf=numeric_limits::max()/2-1; template int tbit(T x){ using U=make_unsigned_t; U y=(U)x; return y?(int)bit_width(y)-1:-1; } template int lbit(T x){ using U=make_unsigned_t; U y=(U)x; return y?(int)countr_zero(y):-1; } template int tbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return -1; if(p>=W-1)return tbit(y); return tbit(y&((U(1)<<(p+1))-1)); } template int lbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return lbit(y); if(p>=W)return -1; return lbit(y&(~U(0)<>(istream&is,i128&x){ string s;is>>s; x=0; int i=0,neg=0; if(s[0]=='-')neg=1,i=1; for(;i<(int)s.size();i++)x=x*10+s[i]-'0'; if(neg)x=-x; return is; } ostream& operator<<(ostream&os,i128 x){ if(x==0)return os<<0; if(x<0)os<<"-"; using u128=__uint128_t; u128 y=x<0?-(u128)x:(u128)x; string s; while(y)s.pb('0'+y%10),y/=10; reverse(all(s)); return os< ostream& operator<<(ostream&os,const pair&p){ return os<<"("< ostream& operator<<(ostream&os,const array&a){ os<<"["; rep(i,N){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const vc&a){ os<<"["; rep(i,a.size()){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const deque&a){ os<<"["; rep(i,a.size()){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const set&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const multiset&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const unordered_set&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const map&m){ os<<"{"; bool f=0; for(auto&x:m){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const unordered_map&m){ os<<"{"; bool f=0; for(auto&x:m){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,queueq){ vca; while(q.size())a.pb(q.front()),q.pop(); return os< ostream& operator<<(ostream&os,stacks){ vca; while(s.size())a.pb(s.top()),s.pop(); return os< ostream& operator<<(ostream&os,priority_queueq){ vca; while(q.size())a.pb(q.top()),q.pop(); return os< void debug_out(const T&x,const Ts&...xs){ cout<sync_with_stdio(0); #ifdef LOCAL cout<0); mod=mod_; m=(i128(1)<<64)/mod; } unsigned reduce(uint64_t x){ assert(mod>0); x-=(((i128)x*m)>>64)*mod; return x struct DynamicModInt{ using u32=uint32_t; using u64=uint64_t; u32 val; DynamicModInt():val(0){} DynamicModInt(ll x){ ll v=x%get_mod(); if(v<0)v+=get_mod(); val=v; } static DynamicModInt raw(int v){ assert(v>=0); DynamicModInt mi; mi.val=v; return mi; } DynamicModInt &operator+=(const DynamicModInt&m){ if((val+=m.val)>=get_mod())val-=get_mod(); return *this; } DynamicModInt &operator-=(const DynamicModInt&m){ if((val+=(get_mod()-m.val))>=get_mod())val-=get_mod(); return *this; } DynamicModInt &operator*=(const DynamicModInt&m){ val=rem(u64(val)*m.val); return *this; } DynamicModInt &operator/=(const DynamicModInt&m){ val=rem(u64(val)*m.inv().val); return *this; } DynamicModInt operator-() const{ return DynamicModInt(val?get_mod()-val:0); } DynamicModInt operator+() const { return *this; } friend DynamicModInt operator+(DynamicModInt lhs, const DynamicModInt& rhs){ return lhs+=rhs; } friend DynamicModInt operator-(DynamicModInt lhs, const DynamicModInt& rhs){ return lhs-=rhs; } friend DynamicModInt operator*(DynamicModInt lhs, const DynamicModInt& rhs){ return lhs*=rhs; } friend DynamicModInt operator/(DynamicModInt lhs,const DynamicModInt&rhs){ return lhs/=rhs; } bool operator==(const DynamicModInt&p) const{ return p.val==val; } bool operator!=(const DynamicModInt&p) const{ return p.val!=val; } DynamicModInt pow(int64_t n) const{ DynamicModInt res(1),mul(val); while(n){ if(n%2)res*=mul; mul*=mul; n/=2; } return res; } friend ostream&operator<<(ostream&os,const DynamicModInt&p){ os<>(istream&is,DynamicModInt&p){ int64_t x; is>>x; p=DynamicModInt(x); return is; } DynamicModInt inv()const{ int64_t a=val,b=get_mod(),u=1,v=0,t; #ifdef LOCAL assert(gcd(a,b)==1); #endif while(b>0){ t=a/b; swap(a-=t*b,b); swap(u-=t*v,v); } return DynamicModInt(u); } inline static u32 rem(u64 x){return BarrettReduction().reduce(x);} static inline int &get_mod(){ static int mod=0; return mod; } static void set_mod(int md){ assert(0 struct BinomHasGetMod:false_type{}; template struct BinomHasGetMod>:true_type{}; template struct Binom{ private: static vector&fact_table(){static vectorv={1};return v;} static vector&invfact_table(){static vectorv={1};return v;} static vector&invs_table(){static vectorv={0};return v;} static int&built_mod(){static int mod=-1;return mod;} public: static void build(int n){ auto&_fact=fact_table(); auto&_invfact=invfact_table(); auto&_invs=invs_table(); if constexpr(BinomHasGetMod::value){ auto mod=mint::get_mod(); if(built_mod()!=mod){ _fact={1}; _invfact={1}; _invs={0}; built_mod()=mod; } } if(n<(int)_fact.size())return; int old=_fact.size(); _fact.resize(n+1); _invfact.resize(n+1); _invs.resize(n+1); if constexpr(BinomHasGetMod::value){ auto mod=mint::get_mod(); for(int i=old;i<=n;i++){ _fact[i]=_fact[i-1]*i; if(i==1)_invs[i]=1; else _invs[i]=-_invs[mod%i]*(mod/i); _invfact[i]=_invfact[i-1]*_invs[i]; } }else{ for(int i=old;i<=n;i++){ _fact[i]=_fact[i-1]*i; _invs[i]=mint(1)/i; _invfact[i]=_invfact[i-1]*_invs[i]; } } } static mint fact(int i){ assert(i>=0); build(i); return fact_table()[i]; } static mint invfact(int i){ assert(i>=0); build(i); return invfact_table()[i]; } static mint inv(int i){ assert(i>0); build(i); return invs_table()[i]; } static mint C(int a,int b){//aCb if(a<0||b<0||a-b<0)return mint(0); build(a); auto&_fact=fact_table(); auto&_invfact=invfact_table(); return _fact[a]*_invfact[b]*_invfact[a-b]; } static mint iC(int a,int b){//1/aCb if(a<0||b<0||a-b<0)return mint(0); build(a); auto&_fact=fact_table(); auto&_invfact=invfact_table(); return _fact[b]*_fact[a-b]*_invfact[a]; } static mint P(int a,int b){ if(a T extgcd(T a, T b, T &x, T &y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } template pair inv(T x,T m){ T a1,a2; T res=extgcd(x,m,a1,a2); T md=m/res; a1=(a1%md+md)%md; return {a1,md}; } template pair mod_solve(T a,T b,T m){//return x s.t. ax=b mod m a%=m,b%=m;if(a<0)a+=m;if(b<0)b+=m; T g=gcd(gcd(a,b),m); a/=g,b/=g,m/=g; if(gcd(a,m)>1)return {-1,-1}; return {(inv(a,m).first*b)%m,inv(a,m).second}; } //https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp.html int64_t mod_sqrt(const int64_t &a, const int64_t &p) { assert(0 <= a && a < p); if (a < 2) return a; using Mint = DynamicModInt<409075245>; Mint::set_mod(p); if (Mint(a).pow((p - 1) >> 1) != 1) return -1; Mint b = 1, one = 1; while (b.pow((p - 1) >> 1) == 1) b += one; int64_t m = p - 1, e = 0; while (m % 2 == 0) m >>= 1, e += 1; Mint x = Mint(a).pow((m - 1) >> 1); Mint y = Mint(a) * x * x; x *= a; Mint z = Mint(b).pow(m); while (y != 1) { int64_t j = 0; Mint t = y; while (t != one) { j += 1; t *= t; } z = z.pow(int64_t(1) << (e - j - 1)); x *= z; z *= z; y *= z; e = j; } return x.val; } #line 3 "lib/math/static-mod-int.hpp" template struct StaticModInt{ static_assert(0=0); StaticModInt mi; mi.val=v; return mi; } StaticModInt &operator+=(const StaticModInt&m){ if((val+=m.val)>=mod)val-=mod; return *this; } StaticModInt &operator-=(const StaticModInt&m){ if((val+=(mod-m.val))>=mod)val-=mod; return *this; } StaticModInt &operator*=(const StaticModInt&m){ val=u64(val)*m.val%mod; return *this; } StaticModInt &operator/=(const StaticModInt&m){ val=u64(val)*m.inv().val%mod; return *this; } StaticModInt operator-() const{ return StaticModInt(mod-val); } StaticModInt operator+() const { return *this; } friend StaticModInt operator+(StaticModInt lhs, const StaticModInt& rhs){ return lhs+=rhs; } friend StaticModInt operator-(StaticModInt lhs, const StaticModInt& rhs){ return lhs-=rhs; } friend StaticModInt operator*(StaticModInt lhs, const StaticModInt& rhs){ return lhs*=rhs; } friend StaticModInt operator/(StaticModInt lhs,const StaticModInt&rhs){ return lhs/=rhs; } bool operator==(const StaticModInt&p) const{ return p.val==val; } bool operator!=(const StaticModInt&p) const{ return p.val!=val; } StaticModInt pow(int64_t n) const{ StaticModInt res(1),mul(val); while(n){ if(n%2)res*=mul; mul*=mul; n/=2; } return res; } friend ostream&operator<<(ostream&os,const StaticModInt&p){ os<>(istream&is,StaticModInt&p){ int64_t x; is>>x; p=StaticModInt(x); return is; } StaticModInt inv()const{ int64_t a=val,b=mod,u=1,v=0,t; #ifdef LOCAL assert(gcd(a,b)==1); #endif while(b>0){ t=a/b; swap(a-=t*b,b); swap(u-=t*v,v); } return StaticModInt(u); } }; #line 3 "a.cpp" using mint=StaticModInt<(int)1e9+7>; void solve(){ LL(n,m); PRT((mint(2).pow(m)-1)/2); } signed main(){ int t=1; // cin >> t; while(t--)solve(); }