Course

题号：NC14319
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Aria正面临算设课程的考试。

设

$F(n)=\prod_{i=1}^{n}\prod_{j=1}^{i}j=\prod_{i=1}^{n}i!$

对于给定的n,m（其中n为质数），求F(n^m)中质因子n的出现次数，即求一个最大的非负整数e满足n^e整除F(n^m)。

由于是算设课的考试，答案当然是对10⁹+7取模的。

一行，两个正整数𝑛，𝑚。

一行，一个整数，质因子𝑛的出现次数，答案对10⁹+ 7取模。

示例1

复制

233 2333

复制

861127073

示例2

复制

2 2

复制

对于10%的数据，𝑛^𝑚≤ 3000。

对于30%的数据，𝑛^𝑚≤ 10⁶。

对于60%的数据，𝑛^𝑚≤ 10¹⁸。

对于80%的数据，𝑚 ≤ 1000。

对于100%的数据，𝑛,𝑚 ≤ 10⁹，𝑛是质数。