令 $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 的答案。
样例一
input
5 3 5 5 4 5 5 3 0 3 2 3
output
295164 295326
样例二
input
10 5 13 11 17 7 9 2 11 11 10 12 7 9 4 15 18 4 9 7 4 2
output
75340090 59089865
限制与约定
共 10 个测试点，只有子问题 1 答案正确将获得 3 分，只有子问题 2 答案正确将获得 6 分，都正确将获得 10 分。
| 测试点编号 | $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 10^{18}$ | $\leq 25$ | ||
| 6 | $\leq 10^3$ | $\leq 10^3$ | $\leq 10$ | |
| 7 | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 10$ | |
| 8 | $\leq 15$ | |||
| 9 | $\leq 20$ | |||
| 10 | $\leq 25$ |
时间限制：$3\texttt{s}$
空间限制：$256\texttt{MB}$
来源
中国国家集训队互测2015 - By 杜瑜皓