Let $N = \prod_{i = 1}^{n} p_i^{a_i}$ and $M = \prod_{i = 1}^{n} p_i^{b_i}$, where $p_i$ are distinct prime numbers.

Find the number of ways to represent $N$ as a product of $k$ positive integers, i.e., the number of solutions to $N = \prod_{i = 1}^k x_i$. The answer should be taken modulo $10^9 + 21$.

For subproblem 1, it is required that for all integers $i$ such that $1 \leq i < k$, $x_i < x_{i + 1}$.

For subproblem 2, it is required that for all integers $i$ such that $1 \leq i < k$, $x_i \leq x_{i + 1}$.

For both subproblems, it is required that for all integers $i$ such that $1 \leq i \leq k$, $x_i \nmid M$, meaning $x_i$ is not a divisor of $M$.

Input

The first line contains two positive integers $n, k$.

The next line contains $n$ non-negative integers, where the $i$-th integer represents $a_i$.

The next line contains $n$ non-negative integers, where the $i$-th integer represents $b_i$.

The primes $p_1, \dots, p_n$ are not provided in the input; clearly, the values of $p_i$ do not affect the answer.

Output

One line containing two integers, representing the answers to subproblem 1 and subproblem 2, respectively.

Examples

Input 1

5 3
5 5 4 5 5
3 0 3 2 3

Output 1

295164 295326

Input 2

10 5
13 11 17 7 9 2 11 11 10 12
7 9 4 15 18 4 9 7 4 2

Output 2

75340090 59089865

Subtasks

There are 10 test cases. Correctly solving only subproblem 1 earns 3 points, only subproblem 2 earns 6 points, and solving both earns 10 points.