Counting Factorizations with Divisor Restrictions

We are given two numbers

[ N = \prod_{i=1}^{n} p_i^{a_i},\quad M = \prod_{i=1}^{n} p_i^{b_i}, ]

where (p_1, p_2, \dots, p_n) are distinct primes. You are also given a positive integer (k) and a parameter (t) (with (t = 1) or (t = 2)). Your task is to count the number of ways to represent (N) as a product of (k) positive integers

[ N = x_1 \times x_2 \times \cdots \times x_k, ]

subject to the following conditions:

1. For all (i) ((1 \le i \le k)), it holds that (x_i \nmid M) (i.e. (x_i) is not a divisor of (M)).
2. Depending on (t) the factors must be ordered as follows:
   • If (t = 1): (x_1 < x_2 < \cdots < x_k) (strictly increasing).
   • If (t = 2): (x_1 \le x_2 \le \cdots \le x_k) (non-decreasing).

Since the answer can be large, output it modulo (10^9+21).

inputFormat

The input consists of four lines:

1. The first line contains three integers \(n\), \(k\), and \(t\) (where \(t = 1\) indicates that the factors must be strictly increasing and \(t = 2\) indicates non-decreasing order).
2. The second line contains \(n\) distinct primes: \(p_1, p_2, \dots, p_n\).
3. The third line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) (the exponents in \(N\)).
4. The fourth line contains \(n\) integers: \(b_1, b_2, \dots, b_n\) (the exponents in \(M\)).

outputFormat

Output a single integer, which is the number of ways to represent \(N\) as a product of \(k\) positive integers obeying the given conditions, taken modulo \(10^9+21\).

sample

2 2 1
2 3
2 2
1 1

1