#pragma region template #include using namespace std; //other #include #include using namespace __gnu_pbds; template using pbds=tree, rb_tree_tag, tree_order_statistics_node_update>; #include using namespace atcoder; #include "atcoder/modint.hpp" using mint = atcoder::modint998244353; using mint2 = atcoder::modint1000000007; #define int long long #define pb push_back #define eb emplace_back #define ep emplace #define len(a) (int)a.size() #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //using using ll=long long; using ld=long double; using ull=unsigned long long; using uint=unsigned; using pcc=pair; using pii=pair; using pll=pair; using pdd=pair; using vi=vector; using vl=vector; using vvi=vector; using vvl=vector; using vvvi=vector; using vvvl=vector; templateusing pqmin=priority_queue,greater>; templateusing pqmax=priority_queue; const ll LINF=0x1fffffffffffffff; const int INF=0x3fffffff; const int MOD=998244353; const int MOD2=1000000007; const ld PI=3.1415926535897932384626433832795028841971; const ld DINF=numeric_limits::infinity(); const ld EPS=1e-9; const ll di[]={0,1,0,-1,1,-1,1,-1}; const ll dj[]={1,0,-1,0,1,1,-1,-1}; template constexpr auto min(T a,T b,T c){ return min(a,min(b,c)); } template constexpr auto min(T... a){ return min(initializer_list>{a...}); } template constexpr auto max(T a,T b,T c){ return max(a,max(b,c)); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0;i(a);) #define rrep4(i,a,b,c)for(ll i=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c) #define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all1(i) begin(i),end(i) #define all2(i,a) begin(i),begin(i)+a #define all3(i,a,b) begin(i)+a,begin(i)+b #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define sum(...) accumulate(all(__VA_ARGS__),0LL) #define dsum(...) accumulate(all(__VA_ARGS__),0.0L) #define Msum(...) accumulate(all(__VA_ARGS__),0_M) #define elif else if #define INT(...) int __VA_ARGS__;input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__) #define STR(...) string __VA_ARGS__;input(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;input(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;input(__VA_ARGS__) int chmax(int &a,int b){ if(ab){a=b;return 1;} else return 0; } //io //in void scan(){} // void scan(int &a){cin>>a;} void scan(unsigned &a){cin>>a;} void scan(long& a){cin>>a;} void scan(long long& a){cin>>a;} void scan(unsigned long long&a){cin>>a;} void scan(char& a){cin>>a;} void scan(float& a){cin>>a;} void scan(double& a){cin>>a;} void scan(long double& a){cin>>a;} void scan(vector& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){cin>>a;} template void scan(vector&); template void scan(array&); template void scan(pair&); template void scan(T(&)[size]); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(deque& a){ for(auto&& i : a) scan(i); } template void scan(array& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } template void scan(T& a){ cin >> a; } void input(){} template void input(Head& head,Tail&... tail){scan(head);input(tail...);} //out void puts(){ putchar(' '); } void puts(bool a){ printf("%d", a); } // void puts(int a){ printf("%d", a); } void puts(unsigned a){ printf("%u", a); } void puts(long a){ printf("%ld", a); } void puts(long long a){ printf("%lld", a); } void puts(unsigned long long a){ printf("%llu", a); } void puts(char a){ printf("%c", a); } void puts(char a[]){ printf("%s", a); } // void puts(const char a[]){ printf("%s", a); } void puts(float a){ printf("%.15f", a); } void puts(double a){ printf("%.15f", a); } void puts(long double a){ printf("%.15Lf", a); } void puts(const string& a){ for(auto&& i : a) puts(i); } template void puts(const complex& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); } template void puts(const vector&); template void puts(const array&); template void puts(const pair& p); template void puts(const T (&)[size]); template void puts(const vector& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const deque& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const set& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const multiset& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const array& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template void puts(const pair& p){ puts(p.first); putchar(' '); puts(p.second); } template void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } } template void puts(const T& a){ cout << a; } int print(){ putchar('\n'); return 0; } template int print(const T& t){ puts(t); putchar('\n'); return 0; } template int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; } #pragma endregion #pragma region commonly used int digitsum(string s){ int res=0; rep(i,(int)s.size()){ res+=s[i]-'0'; } return res; } #pragma endregion //nCk高速 const int mod=1000000007; const int MAX_N = 1000000; int fact[MAX_N + 1], inv_fact[MAX_N + 1]; int mod_pow(int x, int n) { int res = 1; while (n > 0) { if (n & 1) res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; } int mod_inv(int x) { return mod_pow(x, mod - 2); } void nck_init() { fact[0] = inv_fact[0] = 1; for (int i = 1; i <= MAX_N; i++) { fact[i] = (fact[i - 1] * i) % mod; inv_fact[i] = mod_inv(fact[i]); } } //nCk 使う時にnck_init() を必ず入れる。 int nCk(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; int res = fact[n]; res = (res * inv_fact[k]) % mod; res = (res * inv_fact[n - k]) % mod; return res; } vector prime_fac_vec(int n) { vector res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { res.push_back(i); n /= i; } } if (n != 1) res.push_back(n); return res; } map prime_fac_map(int n) { map res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { res[i]++; n /= i; } } if (n != 1) res[n]++; return res; } signed main(){ INT(n,m); if(n