Cho hai số nguyên dương ~X~ và ~Y~. ~X~ có giá trị bằng tích lũy thừa của ~n~ số nguyên tố ~p_1, p_2, ..., p_n~ với số mũ lần lượt là ~a_1, a_2, ..., a_n~ hay ~X~ = ~p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_n^{a_n}~. ~Y~ có giá trị bằng tích lũy thừa của ~m~ số nguyên tố ~q_1, q_2, ..., q_m~ với số mũ lần lượt là ~b_1, b_2, ..., b_m~ hay ~Y~ = ~q_1^{b_1} \cdot q_2^{b_2} \cdot ... \cdot q_m^{b_m}~.

Hỏi có bao nhiêu số nguyên dương ~Z~ thỏa mãn các điều kiện:

• Là ước của số ~X~.

• Là bội của sô ~Y~.

• Tổng số mũ khi phân tích ra thừa số nguyên tố không vượt quá ~k~.

Vì kết quả có thể rất lớn, in ra số lượng số nguyên ~Z~ thỏa mãn chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~k~ ~(1 \leq k \leq 10^5)~.

• Dòng thứ hai chứa số nguyên dương ~n~ ~(1 \leq n \leq 100)~.

• Dòng thứ ba chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \leq a_i \leq 10^5)~.

• Dòng thứ tư chứa ~n~ số nguyên dương phân biệt ~p_1, p_2, ..., p_n~ ~(1 \leq p_i \leq 10^9)~.

• Dòng thứ năm chứa số nguyên dương ~m~ ~(1 \leq m \leq 100)~.

• Dòng thứ sáu chứa ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ ~(1 \leq b_i \leq 10^5)~.

• Dòng cuối cùng chứa ~m~ số nguyên dương phân biệt ~q_1, q_2, ..., q_m~ ~(1 \leq q_i \leq 10^9)~.

Dữ liệu đảm bảo tổng số mũ của ~X~ là ~Y~ không vượt quá ~10^5~.

Output

• Một số duy nhất là số lượng số ~Z~ thỏa mãn sau khi chia lấy dư cho ~10^9+7~.

Subtask

• ~30\%~ số test có ~X, Y \leq 10^6~.

• ~30\%~ số test khác có tổng số mũ của ~X~ và ~Y~ không vượt quá ~k~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
2
2 2
2 3
2
1 1
2 3

Sample Output 1

3

Note

Trong test ví dụ, ~X = 2^2 \times 3^2 = 36~, ~Y = 2 \times 3 = 6~. Các giá trị ~Z~ thỏa mãn là ~6~, ~12~ và ~18~.