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

令 $N = \prod_{i = 1}^{n} p_i^{a_i}$，$M = \prod_{i = 1}^{n} p_i^{b_i}$，其中 $p_i$ 是两两不同的素数。 求将 $N$ 表示成 $k$ 个正整数的乘积的方案数，也就是 $N = \prod_{i = 1}^k x_i$ 的解的个数，答案对 $10^9 + 21$ 取模。 对于子问题 $1$，要求对于所有整数 $i$ 满足 $1 \leq i < k$，都有 $x_i < x_{i + 1}$。 对于子问题 $2$，要求对于所有整数 $i$ 满足 $1 \leq i < k$，都有 $x_i \leq x_{i + 1}$。 对于两个子问题都要求对于所有整数 $i$ 满足 $1 \leq i \leq k$ 都有 $x_i \nmid M$，即 $x_i$ 不是 $M$ 的约数。

第一行两个正整数 $n, k$。 接下来一行 $n$ 个非负整数，第 $i$ 个整数表示 $a_i$。 接下来一行 $n$ 个非负整数，第 $i$ 个整数表示 $b_i$。 输入中没有给出 $p_1, \dots, p_n$，显然 $p_i$ 的取值并不影响答案。

一行两个整数，分别表示子问题 1 和 2 的答案。

| 测试点编号 | $n$ | $a_i$ | $b_i$ | $k$ | |:--------:|:------------:|:------------:|:------------:|:------------:| | 1 | $\leq 5$ | $\leq 5$ | $\leq 5$ | $\leq 3$ | | 2 | $\leq 10$ | $\leq 20$ | $\leq 20$ | $\leq 5$ | | 3 | $= 1$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 25$ | | 4 | $\leq 50$ | $\leq 10^3$ | $= 0$ | $\leq 20$ | | 5 | $\leq 50$ | $\leq 10^{18}$ | $= 0$ | $\leq 25$ | | 6 | $\leq 50$ | $\leq 10^3$ | $\leq 10^3$ | $\leq 10$ | | 7 | $\leq 50$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 10$ | | 8 | $\leq 50$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 15$ | | 9 | $\leq 50$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 20$ | | 10 | $\leq 50$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 25$ |