Submission #4016291
Source Code Expand
/* see function solve() */
/* <rab:include(base.hpp)> */
/* subset of bits/stdc++.h */
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<vector>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define int LL
#define times(n, i) uptil(0, n, i)
#define rtimes(n, i) downto((n) - 1, 0, i)
#define upto(f, t, i) for(auto i##0_to = (t), i = decltype(t)(f); i <= i##0_to; i++)
#define uptil(f, t, i) for(auto i##0_to = (t), i = decltype(t)(f); i < i##0_to; i++)
#define downto(f, t, i) for(auto i##0_to = decltype(f)(t), i = (f); i >= i##0_to; i--)
#define downtil(f, t, i) for(auto i##0_to = decltype(f)(t), i = (f); i > i##0_to; i--)
#define iter(v) begin(v), end(v)
#define citer(v) cbegin(v), cend(v)
#if defined(EBUG) && !defined(ONLINE_JUDGE)
#define debug true
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 2
#define _LIBCPP_DEBUG2 2
#define ln << endl
#define dd(x) cerr << #x << " = " << (x) << ", "
#define ddd(x) cerr << #x << " = " << (x) ln
#else
#define debug false
#define ln << '\n'
#define dd(x) cerr
#define ddd(x) cerr
#endif
#define tb << '\t'
#define sp << ' '
#define db dd
#define dbg ddd
#if __cplusplus >= 201703L
#if debug
#define PARABLE execution::par_unseq,
#else
#define PARABLE execution::seq,
#endif
#else
#define PARABLE /* none */
#endif
#define CS const
#define IL inline
#define RT return
#define TL template
#define lambda [&]
#define foldl accumulate
#define scanl accumulate
typedef struct unit{}unit;
TL<class T> void amax(T&v,const T&a){v=max(v,a);}
TL<class T> void amin(T&v,const T&a){v=min(v,a);}
namespace kpl {
template<class V, class W>
static inline void append(V& v, const W& w) { copy(PARABLE citer(w), back_inserter(v)); }
template<class V>
static inline auto flatten(const V& xss, unsigned reserve_size = 0) {
vector<decltype(*begin(*begin(xss)))> ret;
ret.reserve(reserve_size);
for(const auto& xs : xss) append(ret, xs);
ret.shrink_to_fit();
return move(ret);
}
template<class I>
static inline bool is_in(I x, I l, I r) {
return l <= x && x < r;
}
}
/* <rab:include(util.hpp)> */
#ifndef __cpp_lib_exchange_function
#define __cpp_lib_exchange_function 201304L
TL<class T, class U=T> T exchange(T& t, U&& u) {
T ret = move(t); t = forward<U>(u); return ret;
}
#endif
/* </rab:include(util.hpp)> */
/* <rab:include(mod.hpp)> */
#ifndef MOD
#ifdef MOD9
#define MOD 1000000009
#elif defined MOD998244353
#define MOD 998244353
#else
#define MOD 1000000007
#endif
#endif
/* <rab:include(power.hpp)> */
TL<class T> T power(T x,ULL n){T rt(1);while(n){if(n%2)rt*=x;x*=x;n/=2;}RT rt;}
/* </rab:include(power.hpp)> */
IL int modulo(int a,int m){a%=m;RT a>=0?a:a+m;}
TL<ULL mod=MOD>class MInt{
/*
int with modulo.
`mod` must be a prime for `log`.
`mod` must be coprime to `val` for `inv` and to `m.val` for `operator/` and `operator/=`.
*/
/*! https://ei1333.github.io/luzhiled/snippets/other/mod-int.html */
public:
int val;
MInt():val(0){}
explicit MInt(int v):val(modulo(v,mod)){}
MInt&operator+=(CS MInt&m){val+=m.val;if(val>=mod)val-=mod;RT*this;}
MInt&operator-=(CS MInt&m){val-=m.val;if(val<0)val+=mod;RT*this;}
MInt&operator*=(CS MInt&m){val=val*m.val%mod;RT*this;}
MInt&operator/=(CS MInt&m){val=val*m.inv().val%mod;RT*this;}
MInt operator+(CS MInt&m)CS{RT MInt(*this)+=m;}
MInt operator-(CS MInt&m)CS{RT MInt(*this)-=m;}
MInt operator*(CS MInt&m)CS{RT MInt(*this)*=m;}
MInt operator/(CS MInt&m)CS{RT MInt(*this)/=m;}
MInt operator-()CS{MInt m;m.val=val?mod-val:0;RT m;}
bool operator==(CS MInt&m)CS{RT val==m.val;}
bool operator!=(CS MInt&m)CS{RT val!=m.val;}
//MInt pow(int n)CS{MInt x(*this),rt(1);while(n){if(n%2)rt*=x;x*=x;n/=2;}RT rt;}
MInt pow(int n)CS{RT power(*this,n);}
MInt inv()CS{int a=val,b=mod,x=1,y=0,t;while(b){t=a/b;swap(b,a-=t*b);swap(y,x-=t*y);}RT(MInt)x;}
friend ostream&operator<<(ostream&o,CS MInt<mod>&m){RT o<<m.val;}
friend istream&operator>>(istream&i,MInt<mod>&m){int v;i>>v;m=MInt<mod>(v);RT i;}
};
using mint=MInt<>;
//#pragma rab:gsub \b(\d+)m\b mint(\1)
/* </rab:include(mod.hpp)> */
/* <rab:include(typedefs.hpp)> */
TL<class T> using vec = vector<T>;
TL<class T> using vvec = vec<vec<T>>;
#define VUSE(v,t)using P##v##v=pair<t,t>;using V##v=vec<t>;using W##v=vvec<t>
VUSE(I,int);VUSE(M,mint);VUSE(PII,PII);VUSE(PMM,PMM);VUSE(S,string);
/* </rab:include(typedefs.hpp)> */
/* <rab:include(debug.hpp)> */
TL<class T>
IL istream&operator>>(istream&s,vec<T>&v){for(auto&&p:v)s>>p;RT s;}
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS pair<T,S>&p){RT s<<"("<<p.first<<","<<p.second<<")";}
TL<class T>
IL ostream&operator<<(ostream&,CS vec<T>&);
TL<class T,class S>
IL ostream&operator<<(ostream&,CS map<T,S>&);
#define DEFINE_ITER_OUTPUT(s,x,sep){int i=0;for(CS auto&x##0_elem:x){if(i++)s<<sep;s<<x##0_elem;}RT s;}
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<T>&v)DEFINE_ITER_OUTPUT(s,v,' ')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS map<T,S>&m)DEFINE_ITER_OUTPUT(s,m,' ')
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<vec<T>>&w)DEFINE_ITER_OUTPUT(s,w,'\n')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS vec<map<T,S>>&v)DEFINE_ITER_OUTPUT(s,v,'\n')
/* </rab:include(debug.hpp)> */
void solve();
signed main() {
if(debug) cerr << "MOD: " << (MOD) ln;
if(!debug) {
cin.tie(0);
ios::sync_with_stdio(0);
}
cout << fixed << setprecision(20);
cerr << fixed << setprecision(20);
solve();
return 0;
}
/* </rab:include(base.hpp)> */
/* <rab:include(nck.hpp)> */
/* <rab:include(fact.hpp)> */
/*! https://twitter.com/meguru_comp/status/694207919517077504 */
VM fact, fact_inv;
inline void fact_init(int n) {
int a = fact.size();
if(a > n) return;
fact.resize(n+1);
fact_inv.resize(n+1);
if(a == 0) {
fact[a] = fact_inv[a] = mint(1);
++a;
}
upto(a, n, i) fact[i] = fact[i-1] * mint(i);
fact_inv[n] = fact[n].inv();
downto(n-1, a, i) fact_inv[i] = fact_inv[i+1] * mint(i+1);
}
/* </rab:include(fact.hpp)> */
/*! https://twitter.com/meguru_comp/status/694547019885449216 */
inline mint nCk(int n, int k, bool check_init = true) {
if(check_init && fact.size() <= n) fact_init(n);
if(0 <= k && k <= n) return fact[n] * fact_inv[k] * fact_inv[n-k];
else return mint(0);
}
inline mint nPk(int n, int k, bool check_init = true) {
if(check_init && fact.size() <= n) fact_init(n);
if(0 <= k && k <= n) return fact[n] * fact_inv[n-k];
else return mint(0);
}
/* </rab:include(nck.hpp)> */
/* <rab:include(prime.hpp)> */
map<int, int> prime_factor(int n) {
map<int, int> 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;
}
/* </rab:include(prime.hpp)> */
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
for(auto& pf : prime_factor(abs(N))) {
auto& k = get<1>(pf);
ans *= nCk(k+M-1, M-1);
if(debug) cerr << '#' << __LINE__ ln
<< " pf: " << (pf) ln
<< " k+M-1: " << (k+M-1) ln
<< " M-1: " << (M-1) ln
<< " fact[k+M-1]: " << (fact[k+M-1]) ln
<< " fact_inv[M-1]: " << (fact_inv[M-1]) ln
<< " fact_inv[k]: " << (fact_inv[k]) ln
<< " nCk(k+M-1, M-1): " << (nCk(k+M-1, M-1)) ln;
}
cout << ans ln;
}
/* <rab:gen/> */
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 |
2 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 |
2 ms |
512 KB |
01_rnd_07.txt |
AC |
2 ms |
512 KB |
01_rnd_08.txt |
AC |
4 ms |
2572 KB |
01_rnd_09.txt |
AC |
2 ms |
1152 KB |
01_rnd_10.txt |
AC |
2 ms |
1152 KB |
01_rnd_11.txt |
AC |
3 ms |
1280 KB |
01_rnd_12.txt |
AC |
3 ms |
1664 KB |
01_rnd_13.txt |
AC |
3 ms |
1320 KB |
01_rnd_14.txt |
AC |
2 ms |
1024 KB |
01_rnd_15.txt |
AC |
2 ms |
512 KB |
01_rnd_16.txt |
AC |
3 ms |
1920 KB |
01_rnd_17.txt |
AC |
3 ms |
1792 KB |
01_rnd_18.txt |
AC |
3 ms |
1408 KB |
01_rnd_19.txt |
AC |
2 ms |
452 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 |
768 KB |
01_rnd_23.txt |
AC |
3 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 |
1316 KB |
01_rnd_29.txt |
AC |
4 ms |
2432 KB |
04_primes_01.txt |
AC |
3 ms |
1792 KB |
04_primes_02.txt |
AC |
3 ms |
1792 KB |