Submission #5627439
Source Code Expand
#line 1 "base.hpp"//4
#ifndef __clang__
#pragma GCC optimize ("O3")
#endif
void solve(
#ifdef GCJ_CASE
long long case_id
#endif
);
#if defined(EBUG) && !defined(ONLINE_JUDGE)
#define debug true
#define _GLIBCXX_DEBUG
// #define _LIBCPP_DEBUG 0
#define _LIBCPP_DEBUG2 0
#else
#define NDEBUG
#define debug false
#endif
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<type_traits>
#include<vector>
#include<cassert>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define int LL
#define CS const
#define CX constexpr
#define IL inline
#define OP operator
#define RT return
#define TL template
#define TN typename
#define lambda [&]
#define rep(f,t,i,c,u)for(int Rb_=(t),i=(f);i c Rb_;u(i))
#define upto(f,t,i)rep(f,t,i,<=,++)
#define uptil(f,t,i)rep(f,t,i,<,++)
#define downto(f,t,i)rep(f,t,i,>=,--)
#define downtil(f,t,i)rep(f,t,i,>,--)
#define times(n,i)uptil(0,n,i)
#define rtimes(n,i)downto((n)-1,0,i)
#define iter(v)begin(v),end(v)
#define citer(v)cbegin(v),cend(v)
#define riter(v)rbegin(v),rend(v)
#define criter(v)crbegin(v),crend(v)
#define IF(a,b,c)((a)?(b):(c))
#if debug
#define ln <<endl
#else
#define ln <<'\n'
#endif
#define tb <<'\t'
#define sp <<' '
#line 1 "base_util.hpp"//4b
#define BINOPa(t,u,op)t OP op(CS u&o)CS{RT t(*this)op##=o;}
#define CMPOP(t,op,f1,f2,x)bool OP op(CS t&x)CS{RT f1 op f2;}
#define CMPOPS(t,f1,f2,x)CMPOP(t,==,f1,f2,x)CMPOP(t,!=,f1,f2,x)\
CMPOP(t,<,f1,f2,x)CMPOP(t,<=,f1,f2,x)CMPOP(t,>,f1,f2,x)CMPOP(t,>=,f1,f2,x)
#line 1 "mod.hpp"//4b
#ifndef MOD
#define MOD 1000000007
#endif
#if !defined(FORCE_MOD)&&MOD!=1000000007&&MOD!=1000000009&&MOD!=998244353
#error mod
#endif
#line 1 "power.hpp"//4bm
TL<TN T>IL T power(T x,int n){T r(1);for(;n;n/=2){if(n%2)r*=x;x*=x;}RT r;}IL int pow_mod(int x,int n,int m){int r=1;
for(;n;n/=2){if(n%2)r=r*x%m;x=x*x%m;}RT r;}
#line 2001 "mod.hpp"//4b
IL CX int modulo(int a,int b){a%=b;RT a&&(a>0)!=(b>0)?a+b:a;}IL CX int divide(int a,int b){RT(a-modulo(a,b))/b;}
TL<int d=MOD>struct MInt{
/*!https://ei1333.github.io/luzhiled/snippets/other/mod-int.html*/
int v;CX MInt():v(0){}explicit CX MInt(int i):v(modulo(i,d)){}MInt&OP+=(CS MInt&m){v+=m.v;if(v>=d)v-=d;RT*this;}
MInt&OP-=(CS MInt&m){v-=m.v;if(v<0)v+=d;RT*this;}MInt&OP*=(CS MInt&m){v=v*m.v%d;RT*this;}MInt&OP/=(CS MInt&m){
RT*this*=m.inv();}BINOPa(MInt,MInt,+)BINOPa(MInt,MInt,-)BINOPa(MInt,MInt,*)BINOPa(MInt,MInt,/)MInt OP-()CS{
RT MInt()-=*this;}CMPOP(MInt,==,v,m.v,m)CMPOP(MInt,!=,v,m.v,m)MInt pow(int n)CS{RT power(*this,n);}MInt inv()CS{
int a=v,b=d,x=1,y=0;while(b){swap(y,x-=a/b*y);swap(b,a%=b);}RT(MInt)x;}
friend ostream&OP<<(ostream&o,CS MInt&m){RT o<<m.v;}friend istream&OP>>(istream&i,MInt&m){i>>m.v;m.v%=d;RT i;}};
using mint=MInt<>;CX mint OP"" _m(ULL n){RT mint(n);}CX MInt<998244353>OP"" _m998244353(ULL n){RT MInt<998244353>(n);}
CX MInt<1000000007>OP"" _m1e9_7(ULL n){RT MInt<1000000007>(n);}
CX MInt<1000000009>OP"" _m1e9_9(ULL n){RT MInt<1000000009>(n);}
#line 1 "typedefs.hpp"//4b
using unit = tuple<>;using int128=__int128;using LD=long double;TL<TN T>using vec=vector<T>;
TL<TN T>using vvec=vec<vec<T>>;TL<TN T>using vvvec=vec<vvec<T>>;TL<TN T>using vvvvec=vec<vvvec<T>>;
using VI=vec<int>;using VB=vec<bool>;using HII=map<int, int>;
#line 1 "alias.hpp"//4b
#define EB emplace_back
#define PB push_back
#define foldl accumulate
#define scanl partial_sum
#line 1 "util.hpp"//4b
TL<TN T>IL bool amax(T&v,CS T&a){RT v<a&&(v=a,1);}TL<TN T>IL bool amin(T&v,CS T&a){RT v>a&&(v=a,1);}
TL<TN T>IL int sizeRAB(T t){RT t.size();}
#define size sizeRAB
#define clamp clampRAB
TL<TN T>IL CX CS T&clamp(CS T&a,CS T&l,CS T&r){RT a<l?l:r<a?r:a;}TL<TN V>IL void uniq2(V&v){
v.erase(unique(iter(v)),v.end());}TL<TN V>IL void uniq(V&v){sort(iter(v));uniq2(v);}
#define leftmost_ge lower_bound
#define leftmost_gt upper_bound
namespace rab{TL<TN I>IL bool is_in(I x,I l,I r){RT l<=x&&x<r;}TL<TN T>IL T fetch(CS T&d,CS vec<T>&v,int i){
RT 0<=i&&i<size(v)?v[i]:d;}}
#line 1 "debug.hpp"//4b
TL<TN T>IL istream&OP>>(istream&s,vec<T>&v){for(auto&&p:v)s>>p;RT s;}TL<TN T,TN S>
IL ostream&OP<<(ostream&s,CS pair<T,S>&p){RT s<<"("<<p.first<<","<<p.second<<")";}
#define Rdebug1(sep, ...)IL ostream& OP<<(ostream&s,CS __VA_ARGS__&v){\
int i=0;for(CS auto&e:v){i++&&s<<sep;s<<e;}RT s;}
TL<TN T>Rdebug1(' ',vec<T>)TL<TN T,TN S>Rdebug1(' ',map<T,S>)TL<TN T>Rdebug1('\n',vvec<T>)
TL<TN T,TN S>Rdebug1('\n',vec<map<T,S>>)
#line 6001 "base.hpp"//4
signed main(){if(debug)cerr<<"MOD: "<<MOD ln;else cin.tie(0),cerr.tie(0),ios::sync_with_stdio(0);
auto p=setprecision(20);cout<<fixed<<p;cerr<<fixed<<p;
#ifdef GCJ_CASE
int T;cin>>T;times(T,t){cout<<"Case #"<<t+1<<": ";solve(t);}
#else
solve();
#endif
RT 0;}
#line 1 "fact.hpp"//4n
/*!https://twitter.com/meguru_comp/status/694207919517077504*/
TL<int m=MOD>struct Fact{using M=MInt<m>;int n;vec<M>f,inv;Fact(int k){n=0;extend(k);}void extend(int k){if(n<k){
f.resize(k+1);inv.resize(k+1);f[0]=inv[0]=M(1);n+=!n;upto(n,k,i)f[i]=f[i-1]*M(i);inv[k]=f[k].inv();downto(k-1,n,i)
inv[i]=inv[i+1]*M(i+1);n=k;}}M OP[](int i)CS{assert(0<=i&&i<=n);RT f[i];}};
#line 2001 "nck.hpp"//4
/*!https://twitter.com/meguru_comp/status/694547019885449216*/
TL<int m>IL MInt<m>nCk(int n,int k,CS Fact<m>&f){RT IF(0<=k&&k<=n,f[n]*f.inv[k]*f.inv[n-k],MInt<m>(0));}TL<int m>
IL MInt<m>nPk(int n,int k,CS Fact<m>&f){RT IF(0<=k&&k<=n,f[n]*f.inv[n-k],MInt<m>(0));}
#line 1 "power_128.hpp"//4p
using int128=__int128;
int128 pow_mod128(int128 x,int n,int m){int128 rt=1;for(;n;n/=2){if(n%2)rt=rt*x%m;x=x*x%m;}RT rt;}
#line 2001 "prime.hpp"//4
/*!
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
http://joisino.hatenablog.com/entry/2017/08/03/210000
https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
*/
VI rab_prime_mr_as = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
bool is_prime(int n) {
assert(n >= 0);
if(n <= 3) return n >= 2;
if(n % 2 == 0 || n % 3 == 0) return false;
if(n < (1<<28)) {
for(int i = 5; i * i <= n; i += 6) {
if(n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
} else {
int d = n - 1, s1 = -1;
while(d % 2 == 0) { d /= 2; ++s1; }
for(int a : rab_prime_mr_as) {
if(n == a) return true;
int128 f = pow_mod128(a, d, n);
if(f == 1 || f == n - 1) continue;
times(s1, r) {
f = f * f % n;
if(f == n - 1) goto next_a;
}
return false;
next_a:;
}
return true;
}
}
/* O(NloglogN) */
VB are_primes(int n) {
assert(n >= 0);
VB ret(n + 1, true);
for(int j = 0; j <= n; j += 2) ret[j] = false;
if(n > 0) ret[1] = false;
for(int i = 3; i * i <= n; i += 2)
if(ret[i])
for(int j = i * i; j <= n; j += i * 2)
ret[j] = false;
return ret;
}
HII prime_factor(int n) {
HII ret;
if(n <= 1) return ret;
#define rab_prime_factor_loop_body(x) \
while(n % (x) == 0) { ++ret[(x)]; n /= (x); }
rab_prime_factor_loop_body(2);
rab_prime_factor_loop_body(3);
for(int i = 5; i * i <= n; i += 6) {
rab_prime_factor_loop_body(i);
rab_prime_factor_loop_body(i + 2);
}
if(n > 1) ++ret[n];
return ret;
}
#line 3001 "4.cpp"//
void solve() {
// NM
/* <foxy.memo-area> */
int N;int M;cin>>N;cin>>M;
/* </foxy.memo-area> */
mint ans = mint(2).pow(M-1); // (-1)^x
Fact<> f(32 + M);
for(auto& pf : prime_factor(abs(N))) {
auto & k = get<1>(pf);
ans *= nCk(k+M-1, M-1, f);
// dd pf; k+M-1; M-1; fact[k+M-1]; fact_inv[M-1]; fact_inv[k]; nCk(k+M-1, M-1);
}
cout << ans ln;
}
Submission Info
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt |
Case Name |
Status |
Exec Time |
Memory |
00_max.txt |
AC |
3 ms |
1792 KB |
00_max2.txt |
AC |
3 ms |
1792 KB |
00_max3.txt |
AC |
3 ms |
1792 KB |
00_min.txt |
AC |
1 ms |
256 KB |
00_sample_01.txt |
AC |
1 ms |
256 KB |
00_sample_02.txt |
AC |
1 ms |
256 KB |
00_sample_03.txt |
AC |
1 ms |
256 KB |
00_sample_04.txt |
AC |
1 ms |
256 KB |
01_rnd_00.txt |
AC |
2 ms |
896 KB |
01_rnd_01.txt |
AC |
1 ms |
384 KB |
01_rnd_02.txt |
AC |
1 ms |
256 KB |
01_rnd_03.txt |
AC |
2 ms |
896 KB |
01_rnd_04.txt |
AC |
2 ms |
768 KB |
01_rnd_05.txt |
AC |
2 ms |
896 KB |
01_rnd_06.txt |
AC |
1 ms |
512 KB |
01_rnd_07.txt |
AC |
1 ms |
512 KB |
01_rnd_08.txt |
AC |
3 ms |
1792 KB |
01_rnd_09.txt |
AC |
2 ms |
1152 KB |
01_rnd_10.txt |
AC |
2 ms |
1152 KB |
01_rnd_11.txt |
AC |
2 ms |
1280 KB |
01_rnd_12.txt |
AC |
3 ms |
1664 KB |
01_rnd_13.txt |
AC |
2 ms |
896 KB |
01_rnd_14.txt |
AC |
2 ms |
1024 KB |
01_rnd_15.txt |
AC |
2 ms |
512 KB |
01_rnd_16.txt |
AC |
2 ms |
1280 KB |
01_rnd_17.txt |
AC |
3 ms |
1792 KB |
01_rnd_18.txt |
AC |
2 ms |
1408 KB |
01_rnd_19.txt |
AC |
1 ms |
384 KB |
01_rnd_20.txt |
AC |
2 ms |
1024 KB |
01_rnd_21.txt |
AC |
2 ms |
1024 KB |
01_rnd_22.txt |
AC |
2 ms |
640 KB |
01_rnd_23.txt |
AC |
2 ms |
1280 KB |
01_rnd_24.txt |
AC |
3 ms |
1408 KB |
01_rnd_25.txt |
AC |
3 ms |
1664 KB |
01_rnd_26.txt |
AC |
2 ms |
1152 KB |
01_rnd_27.txt |
AC |
2 ms |
896 KB |
01_rnd_28.txt |
AC |
2 ms |
896 KB |
01_rnd_29.txt |
AC |
3 ms |
1664 KB |
04_primes_01.txt |
AC |
3 ms |
1792 KB |
04_primes_02.txt |
AC |
3 ms |
1792 KB |