题目描述

我们先引入几个之后需要使用的定义：

• 令 $\texttt{prime(x)}$ 表示 $x$ 的所有质因子组成的集合。例如：

  • $\texttt{prime(140)} = \{2, 5, 7\}$
  • $\texttt{prime(169)} = \{13\}$

• 令 $g(x, p)$ 表示最大的 $p^k$（其中 $k$ 是整数），使得 $x$ 是 $p^k$ 的倍数。例如：

  • $g(45, 3) = 9$（$45$ 是 $3^2=9$ 的倍数，但不是 $3^3=27$ 的倍数）
  • $g(63, 7) = 7$（$63$ 是 $7^1=7$ 的倍数，但不是 $7^2=49$ 的倍数）
  • $g(70,2)=2$（$70$ 是 $2^1=2$ 的倍数，但不是 $2^2=4$ 的倍数）

• 定义 $f(x, y)$ 为 $g(y, p)$ 在所有 $p \in \texttt{prime(x)}$ 下的乘积：

  • $f(x, y) = \prod_{p \in \texttt{prime(x)}} g(y, p)$，通俗解释 $f(x,y)$ 的含义为 $x$ 的所有质因子 $p$ 的 $g(y,p)$ 的乘积。
  • 例如：
    • $f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10$
    • $f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63$

---

你现在给定两个整数 $x$ 和 $n$，请你计算如下表达式的结果并对 $10^9+7$ 取模后输出：

$$f(x, 1) \times f(x, 2) \times \ldots \times f(x, n) \bmod (10^9 + 7) $$

输入格式

第一行输入 $x$ 和 $n$。

输出格式

输出一个整数，为 $f(x, 1) \times f(x, 2) \times \ldots \times f(x, n)$ 对 $10^9 + 7$ 取模

10 2

2

20190929 1605

363165664

947 987654321987654321

593574252

提示

样例 1 解释

在第一个样例中，$f(10, 1) = g(1, 2) \times g(1, 5) = 1$，$f(10, 2) = g(2, 2) \times g(2, 5) = 2$，因此答案为 $1 \times 2 = 2$。

数据范围

对于 $100\%$ 的数据，$2 \le x \le 10^9$，$1 \le n \le 10^{18}$，所有输入值均为整数。

$\text{Subtask}$	分值	特殊性质
$1$	$10$	$n=1$
$2$	$30$	$x,n\le 10^2$
$3$	$60$	无