令 $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 分。

时间限制：$3\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 杜瑜皓

下载

样例数据下载