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~.
Bình luận