Language: C++

#include<iostream>
#include<vector>
#include<cstdint>
using namespace std;

const int MOD = 1000000007; // 今回使う余り
class Factorial;
class ModInt;

class Factorial{
	private:
		int64_t mod;
		int64_t n;
		vector<int64_t> fac, in, fin;
		void calc();
		int64_t rem(int64_t a) {
			if (mod == 0) return a;
			return (a % mod + mod) % mod;
		}
	public:
		Factorial(int64_t mod, int64_t n);
		int64_t add(int64_t a, int64_t b);
		int64_t sub(int64_t a, int64_t b);
		int64_t mul(int64_t a, int64_t b);
		int64_t div(int64_t a, int64_t b);
		int64_t rem(int64_t a, int64_t b);
		int64_t or(int64_t a, int64_t b);
		int64_t and(int64_t a, int64_t b);
		int64_t xor(int64_t a, int64_t b);
		int64_t lshift(int64_t a, int64_t b);
		int64_t rshift(int64_t a, int64_t b);
		int64_t pow(int64_t a, int64_t b);
		int64_t hom(int64_t a, int64_t b);
		int64_t comb(int64_t a, int64_t b);
		int64_t perm(int64_t a, int64_t b);
		int64_t fact(int64_t a);
		int64_t fInv(int64_t a);
		int64_t inv(int64_t a);
		int64_t getMod() {return mod;}
		ModInt create(int64_t n);
		ModInt create() {return create(0);}
};

/**
 * 剰余を計算するための専用のIntクラスです。
 * 
 */
class ModInt {
	private:
		Factorial *f;
		int64_t n;
	public:
		friend class Factorial;
		friend istream& operator>>(istream &s, ModInt &i);
		friend ostream& operator<<(ostream &s, const ModInt &i);
		ModInt (Factorial *f) {ModInt::f = f, n = 0;}
		ModInt (Factorial *f, int64_t n) {ModInt::f = f, ModInt::n = n;}
		inline operator int64_t() const{return n;}
		inline ModInt& operator++() {n = (*f).add(n, 1); return *this;}
		const ModInt operator++(int) {const ModInt ret = *this; ++(*this); return ret;}
		inline ModInt& operator--() {n = (*f).sub(n, 1); return *this;}
		const ModInt operator--(int) {const ModInt ret = *this; --(*this); return ret;}
		inline const ModInt operator+() const{ return *this;}
		const ModInt operator-() const{ return (*f).create(-n);}
		inline ModInt& operator+=(const int64_t& x) {n = (*f).add(n, x); return *this;}
		inline ModInt& operator+(const ModInt& x) { return ModInt(*this) += x;}
		inline ModInt& operator-=(const int64_t& x) {n = (*f).sub(n, x); return *this;}
		inline ModInt& operator-(const ModInt& x) { return ModInt(*this) -= x;}
		inline ModInt& operator*=(const int64_t& x) {n = (*f).mul(n, x); return *this;}
		inline ModInt& operator*(const ModInt& x) { return ModInt(*this) *= x;}
		inline ModInt& operator/=(const int64_t& x) {n = (*f).div(n, x); return *this;}
		inline ModInt& operator/(const ModInt& x) { return ModInt(*this) /= x;}
		inline ModInt& operator%=(const int64_t& x) {n = (*f).rem(n, x); return *this;}
		inline ModInt& operator%(const ModInt& x) { return ModInt(*this) %= x;}
		inline ModInt& operator|=(const int64_t& x) {n = (*f).or(n, x); return *this;}
		inline ModInt& operator|(const ModInt& x) { return ModInt(*this) |= x;}
		inline ModInt& operator&=(const int64_t& x) {n = (*f).and(n, x); return *this;}
		inline ModInt& operator&(const ModInt& x) { return ModInt(*this) &= x;}
		inline ModInt& operator^=(const int64_t& x) {n = (*f).xor(n, x); return *this;}
		inline ModInt& operator^(const ModInt& x) { return ModInt(*this) ^= x;}
		inline ModInt& operator<<=(const int64_t& x) {n = (*f).lshift(n, x); return *this;}
		inline ModInt& operator<<(const ModInt& x) { return ModInt(*this) <<= x;}
		inline ModInt& operator>>=(const int64_t& x) {n = (*f).rshift(n, x); return *this;}
		inline ModInt& operator>>(const ModInt& x) { return ModInt(*this) >>= x;}
		ModInt pow(ModInt x) { return *(new ModInt(f, (*f).pow(n, x)));}
		ModInt H(ModInt x) {return *(new ModInt(f, (*f).hom(n, x)));}
		ModInt C(ModInt x) {return *(new ModInt(f, (*f).comb(n, x)));}
		ModInt P(ModInt x) {return *(new ModInt(f, (*f).perm(n, x)));}
		ModInt fact() {return *(new ModInt(f, (*f).fact(n)));}
};

istream& operator>>(istream &s, ModInt &i) {
	s >> i.n;
	return s;
}

ostream& operator<<(ostream &s, const ModInt& i) {
	s << i.n;
	return s;
}

ModInt Factorial::create(int64_t n) {
	return *(new ModInt(this, rem(n)));
}

/**
 * 関数の初期化を行います。この時に空間O(n)と計算時間O(n)が必要なことに注意してください。
 * @param mod 用いる余り ※必ず素数にすること
 * @param n 用意する階乗の範囲
 */
Factorial::Factorial(int64_t mod, int64_t n) {
	if (mod == 0) n = 0;
	if (n <= 0) n = 1;
	Factorial::mod = mod;
	Factorial::n = n;
	fac.resize(n + 1, 1);
	in.resize(n + 1, 1);
	fin.resize(n + 1, 1);
	calc();
}

void Factorial::calc() {
	for (int64_t i = 2;i <= n;++ i) {
		fac[i] = mul(fac[i - 1], i);
		in[i] = mod - mul(in[mod % i], mod / i);
		fin[i] = mul(fin[i - 1], in[i]);
	}
}

/**
 * a+bをmod環境下で返します。
 * @param a 足す値
 * @param b 足される値
 * @return (a + b) % mod
 */
int64_t Factorial::add(int64_t a, int64_t b) {
	return rem(a + b);
}

/**
 * a-bをmod環境下で返します。
 * @param a 引く値
 * @param b 引かれる値
 * @return (a - b) % mod
 */
int64_t Factorial::sub(int64_t a, int64_t b) {
	return rem(a - b);
}

/**
 * a*bをmod環境下で返します。
 * @param a 掛ける値
 * @param b 掛けられる値
 * @return (a * b) % mod
 */
int64_t Factorial::mul(int64_t a, int64_t b) {
	return rem(a * b);
}

/**
 * a/bをmod環境下で返します。O(log(mod))な点にご注意ください
 * @param a 割る値
 * @param b 割られる値
 * @return (a / b) % mod
 */
int64_t Factorial::div(int64_t a, int64_t b) {
	if (b <= n) return mul(a, in[b]);
	return mul(a, pow(b, mod - 2));
}

/**
 * a|bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a | b
 */
int64_t Factorial::or(int64_t a, int64_t b) {
	return rem(a | b);
}

/**
 * a&bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a & b
 */
int64_t Factorial::and(int64_t a, int64_t b) {
	return a & b;
}

/**
 * a^bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a ^ b
 */
int64_t Factorial::xor(int64_t a, int64_t b) {
	return rem(a ^ b);
}

/**
 * a<<bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a << b
 */
int64_t Factorial::lshift(int64_t a, int64_t b) {
	return mul(a, pow(2, b));
}
/**
 * a>>bを返します。
 * @param a 左辺
 * @param b 右辺
 * @return a >> b
 */
int64_t Factorial::rshift(int64_t a, int64_t b) {
	return div(a, pow(2, b));
}

/**
 * a%bを返します。
 * @param a 割る値
 * @param b 割られる値
 * @return a % b
 */
int64_t Factorial::rem(int64_t a, int64_t b) {
	return a % b;
}

/**
 * aのb乗をmod環境下で返します。
 * @param a 底
 * @param b 冪指数
 * @return pow(a, b) % mod
 */
int64_t Factorial::pow(int64_t a, int64_t b) {
	if (b < 0) return pow(a, b + mod - 1);
	switch(b) {
		case 0: return 1;
		case 1: return a;
		case 2: return mul(a, a);
	}
	return mul(pow(pow(a, b >> 1), 2), pow(a, b & 1));
}

/**
 * aHb(重複組み合わせ)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aHb) % mod
 */
int64_t Factorial::hom(int64_t a, int64_t b) {
	return comb(a + b - 1, b);
}

/**
 * aCb(組み合わせ)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aCb) % mod
 */
int64_t Factorial::comb(int64_t a, int64_t b) {
	return mul(perm(a, b), fInv(b));
}

/**
 * aPb(順列)をmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aPb) % mod
 */
int64_t Factorial::perm(int64_t a, int64_t b) {
	return mul(fact(a), fInv(a - b));
}

/**
 * a!をmod環境下で返します。
 * @param a 計算する値
 * @return a! % mod
 */
int64_t Factorial::fact(int64_t a) {
	if (a <= n) return fac[a];
	int64_t ret = fac[n];
	for (int64_t i = n;i < a;++ i) ret = mul(ret, i + 1);
	return ret;
}

/**
 * a!の-1乗をmod環境下で返します。
 * @param a 計算する値
 * @return pow(a!, -1) % mod
 */
int64_t Factorial::fInv(int64_t a) {
	if (a <= n) return fin[a];
	return pow(fact(a), mod - 2);
}

/**
 * aの-1乗をmod環境下で返します。
 * @param a 計算する値
 * @return pow(a, -1) % mod
 */
int64_t Factorial::inv(int64_t a) {
	if (a <= n) return in[a];
	return pow(a, -1);
}
int main() {
	int N, M;
	cin >> N >> M;
	Factorial f(MOD, 100000);
	ModInt ans(&f, 1);
	vector<pair<int, int> > primes; // 素因数分解の結果
	for (int i = 2, c;i * i <= M;++ i) { // 試し割り
		c = 0; // cは割った回数
		while (M % i == 0) {
			++ c;
			M /= i;
		}
		if (c != 0) primes.push_back(make_pair(i, c));
	}
	if (M > 1) primes.push_back(make_pair(M, 1));
	
	for (int i = 0;i < primes.size();++ i) {
		ans *= f.hom(N, primes[i].second);
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

要するに？Mを素因数分解します。
例えばサンプル1だと、6を素因数分解すると2と3です
後は、全ての要素を1にした数列aに対しこの数を割り振る方法なので、割り振り方を考えます
サンプル2だと、12=2^2*3なのでこれを考えてみましょう
まず3はN通り、次に2を2つ割り振る方法はNH2=(N+1)C2=6通り
結論から言うと、Mの素因数分解した結果がΠ(x_i)^(y_i)ならばΠ(x_i)H(y_i)です
*/

Compiler output:
a.cc:27:25: error: expected unqualified-id before 'or' token
   27 |                 int64_t or(int64_t a, int64_t b);
      |                         ^~
a.cc:28:36: error: expected ')' before 'a'
   28 |                 int64_t and(int64_t a, int64_t b);
      |                            ~       ^~
      |                                    )
a.cc:29:25: error: expected unqualified-id before 'xor' token
   29 |                 int64_t xor(int64_t a, int64_t b);
      |                         ^~~
a.cc:41:33: error: return type 'class ModInt' is incomplete
   41 |                 ModInt create() {return create(0);}
      |                                 ^
a.cc: In member function 'void Factorial::create()':
a.cc:41:47: error: invalid use of incomplete type 'class ModInt'
   41 |                 ModInt create() {return create(0);}
      |                                         ~~~~~~^~~
a.cc:8:7: note: forward declaration of 'class ModInt'
    8 | class ModInt;
      |       ^~~~~~
a.cc: In member function 'ModInt& ModInt::operator|=(const int64_t&)':
a.cc:75:71: error: expected unqualified-id before 'or' token
   75 |                 inline ModInt& operator|=(const int64_t& x) {n = (*f).or(n, x); return *this;}
      |                                                                       ^~
a.cc: In member function 'ModInt& ModInt::operator&=(const int64_t&)':
a.cc:77:71: error: expected unqualified-id before 'and' token
   77 |                 inline ModInt& operator&=(const int64_t& x) {n = (*f).and(n, x); return *this;}
      |                                                                       ^~~
a.cc: In member function 'ModInt& ModInt::operator^=(const int64_t&)':
a.cc:79:71: error: expected unqualified-id before 'xor' token
   79 |                 inline ModInt& operator^=(const int64_t& x) {n = (*f).xor(n, x); return *this;}
      |                                                                       ^~~
a.cc: At global scope:
a.cc:177:20: error: expected unqualified-id before 'or' token
  177 | int64_t Factorial::or(int64_t a, int64_t b) {
      |                    ^~
a.cc:187:20: error: expected unqualified-id before 'and' token
  187 | int64_t Factorial::and(int64_t a, int64_t b) {
      |                    ^~~
a.cc:197:20: error: expected unqualified-id before 'xor' token
  197 | int64_t Factorial::xor(int64_t a, int64_t b) {
      |                    ^~~