#P11739. [集训队互测 2015] 普罗达科特

[集训队互测 2015] 普罗达科特

题目描述

N=i=1npiaiN = \prod_{i = 1}^{n} p_i^{a_i}M=i=1npibiM = \prod_{i = 1}^{n} p_i^{b_i},其中 pip_i 是两两不同的素数。

求将 NN 表示成 kk 个正整数的乘积的方案数,也就是 N=i=1kxiN = \prod_{i = 1}^k x_i 的解的个数,答案对 109+2110^9 + 21 取模。

对于子问题 11,要求对于所有整数 ii 满足 1i<k1 \leq i < k,都有 xi<xi+1x_i < x_{i + 1}

对于子问题 22,要求对于所有整数 ii 满足 1i<k1 \leq i < k,都有 xixi+1x_i \leq x_{i + 1}

对于两个子问题都要求对于所有整数 ii 满足 1ik1 \leq i \leq k 都有 xiMx_i \nmid M,即 xix_i 不是 MM 的约数。

输入格式

第一行两个正整数 n,kn, k

接下来一行 nn 个非负整数,第 ii 个整数表示 aia_i

接下来一行 nn 个非负整数,第 ii 个整数表示 bib_i

输入中没有给出 p1,,pnp_1, \dots, p_n,显然 pip_i 的取值并不影响答案。

输出格式

一行两个整数,分别表示子问题 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

提示

测试点编号 nn aia_i bib_i kk
1 5\leq 5 3\leq 3
2 10\leq 10 20\leq 20 5\leq 5
3 =1= 1 1018\leq 10^{18} 25\leq 25
4 50\leq 50 103\leq 10^3 =0= 0 20\leq 20
5 1018\leq 10^{18} 25\leq 25
6 103\leq 10^3 10\leq 10
7 1018\leq 10^{18}
8 15\leq 15
9 20\leq 20
10 25\leq 25