Submission #5293323
Source Code Expand
// aribon2-3-8_c
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()
#define INF ((1 << 29)-1)
#define MOD (1000000007)
#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;
int mod_pow(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll factorial[200001];
void make_factorial(int mo){ factorial[0] = 1; REPN(i, 1, 200001) factorial[i] = (i * factorial[i-1]) % mo; }
ll nCk(int n, int k, int mo){
ll a = factorial[n];
ll b = factorial[n-k] * factorial[k] % mo;
ll b_inv = mod_pow(b, mo-2, mo);
return a * b_inv % mo;
}
void factorize(int n, map<int, int> &res){
int sqrt_n = (int) sqrt(n);
REPN(i, 2, sqrt_n+1){
int cnt = 0;
while (n % i == 0){
cnt++;
n /= i;
}
if (cnt > 0){
res[i] = cnt;
}
}
if (n > 1){
res[n] = 1;
}
}
int main() {
#ifdef LOCAL
ifstream in("../arg.txt");
cin.rdbuf(in.rdbuf());
#endif
make_factorial(MOD);
int N, M;
cin >> N >> M;
map<int, int> factorize_res;
factorize(abs(N), factorize_res);
ll ans = 1;
for (auto mp: factorize_res){
int cnt = mp.second;
ans *= nCk(M + cnt - 1, cnt, MOD);
ans %= MOD;
}
ll tmp = 0;
if (N > 0) {
REP(i, M){
if (i * 2 > M) break;
tmp += nCk(M, i * 2, MOD);
tmp %= MOD;
}
} else {
REP(i, M){
if (i * 2 + 1 > M) break;
tmp += nCk(M, i * 2 + 1, MOD);
tmp %= MOD;
}
}
print(ans * tmp % MOD);
return 0;
}
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 |
11 ms |
1792 KB |
00_max2.txt |
AC |
11 ms |
1792 KB |
00_max3.txt |
AC |
11 ms |
1792 KB |
00_min.txt |
AC |
3 ms |
1792 KB |
00_sample_01.txt |
AC |
3 ms |
1792 KB |
00_sample_02.txt |
AC |
3 ms |
1792 KB |
00_sample_03.txt |
AC |
3 ms |
1792 KB |
00_sample_04.txt |
AC |
3 ms |
1792 KB |
01_rnd_00.txt |
AC |
6 ms |
1792 KB |
01_rnd_01.txt |
AC |
4 ms |
1792 KB |
01_rnd_02.txt |
AC |
3 ms |
1792 KB |
01_rnd_03.txt |
AC |
6 ms |
1792 KB |
01_rnd_04.txt |
AC |
5 ms |
1792 KB |
01_rnd_05.txt |
AC |
6 ms |
1792 KB |
01_rnd_06.txt |
AC |
4 ms |
1792 KB |
01_rnd_07.txt |
AC |
4 ms |
1792 KB |
01_rnd_08.txt |
AC |
11 ms |
1792 KB |
01_rnd_09.txt |
AC |
7 ms |
1792 KB |
01_rnd_10.txt |
AC |
8 ms |
1792 KB |
01_rnd_11.txt |
AC |
8 ms |
1792 KB |
01_rnd_12.txt |
AC |
10 ms |
1792 KB |
01_rnd_13.txt |
AC |
6 ms |
1792 KB |
01_rnd_14.txt |
AC |
7 ms |
1792 KB |
01_rnd_15.txt |
AC |
4 ms |
1792 KB |
01_rnd_16.txt |
AC |
8 ms |
1792 KB |
01_rnd_17.txt |
AC |
11 ms |
1792 KB |
01_rnd_18.txt |
AC |
9 ms |
1792 KB |
01_rnd_19.txt |
AC |
4 ms |
1792 KB |
01_rnd_20.txt |
AC |
7 ms |
1792 KB |
01_rnd_21.txt |
AC |
7 ms |
1792 KB |
01_rnd_22.txt |
AC |
4 ms |
1792 KB |
01_rnd_23.txt |
AC |
8 ms |
1792 KB |
01_rnd_24.txt |
AC |
9 ms |
1792 KB |
01_rnd_25.txt |
AC |
10 ms |
1792 KB |
01_rnd_26.txt |
AC |
7 ms |
1792 KB |
01_rnd_27.txt |
AC |
6 ms |
1792 KB |
01_rnd_28.txt |
AC |
6 ms |
1792 KB |
01_rnd_29.txt |
AC |
10 ms |
1792 KB |
04_primes_01.txt |
AC |
11 ms |
1792 KB |
04_primes_02.txt |
AC |
11 ms |
1792 KB |