质因数零件分组
质因数零件分组
题目描述
正整数 n 含 r 种不同质因数。把 n 分成有序的 k 个正整数，其乘积为 n 且任意两数互质。每个完整质数幂块必须整体分给且只分给一个位置。
输入格式
第一行输入 r、k，满足 1≤r≤100000、1≤k≤10^9。接下来 r 行输入不同质数 p 及正指数 e。
输出格式
输出方案数 k^r 对1000000007取模的结果。允许某个位置分得1。
样例
输入
1 2
2 3
输出
2
正整数 n 含 r 种不同质因数。把 n 分成有序的 k 个正整数，其乘积为 n 且任意两数互质。每个完整质数幂块必须整体分给且只分给一个位置。
第一行输入 r、k，满足 1≤r≤100000、1≤k≤10^9。接下来 r 行输入不同质数 p 及正指数 e。
输出方案数 k^r 对1000000007取模的结果。允许某个位置分得1。
1 2
2 3
2