题目描述
令 N=∏i=1npiai,M=∏i=1npibi,其中 pi 是两两不同的素数。
求将 N 表示成 k 个正整数的乘积的方案数,也就是 N=∏i=1kxi 的解的个数,答案对 109+21 取模。
对于子问题 1,要求对于所有整数 i 满足 1≤i<k,都有 xi<xi+1。
对于子问题 2,要求对于所有整数 i 满足 1≤i<k,都有 xi≤xi+1。
对于两个子问题都要求对于所有整数 i 满足 1≤i≤k 都有 xi∤M,即 xi 不是 M 的约数。
输入格式
第一行两个正整数 n,k。
接下来一行 n 个非负整数,第 i 个整数表示 ai。
接下来一行 n 个非负整数,第 i 个整数表示 bi。
输入中没有给出 p1,…,pn,显然 pi 的取值并不影响答案。
输出格式
一行两个整数,分别表示子问题 1 和 2 的答案。
5 3
5 5 4 5 5
3 0 3 2 3
295164 295326
10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2
75340090 59089865
提示
测试点编号 |
n |
ai |
bi |
k |
1 |
≤5 |
≤3 |
2 |
≤10 |
≤20 |
≤5 |
3 |
=1 |
≤1018 |
≤25 |
4 |
≤50 |
≤103 |
=0 |
≤20 |
5 |
≤1018 |
≤25 |
6 |
≤103 |
≤10 |
7 |
≤1018 |
8 |
≤15 |
9 |
≤20 |
10 |
≤25 |