Đếm mảng

Trong một buổi thực tập tại bệnh viện, FullHouse Dev được giao nhiệm vụ xây dựng hệ thống quản lý thuốc. Để kiểm tra khả năng tư duy logic của họ, người hướng dẫn đã đưa ra một bài toán thú vị về việc đếm các mảng đặc biệt.

Bài toán

Cho một số nguyên \(N\). Bạn cũng được cho \(Q\) truy vấn thuộc loại sau:

Xác định số lượng mảng khác biệt có kích thước \(K\) thỏa mãn các điều kiện:

• Mỗi phần tử trong mảng là số nguyên tố
• Tích của tất cả các phần tử trong mảng bằng \(N\)
• Mảng tạo thành là đối xứng

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa số nguyên \(Q\)
• Dòng tiếp theo chứa \(Q\) số nguyên cách nhau bởi dấu cách, biểu thị giá trị \(K\) cho mỗi truy vấn

OUTPUT FORMAT:

• In ra \(Q\) số nguyên cách nhau bởi dấu cách biểu thị kết quả cho \(Q\) truy vấn theo modulo \(10^9 + 7\)

Ràng buộc:

• \(1 \leq N \leq 10^{12}\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq K \leq 10^5\)

Ví dụ

INPUT

10
2
3 4

OUTPUT

7 7

Giải thích

Với truy vấn 1 (K = 3): Các mảng thỏa mãn điều kiện là các mảng đối xứng có tích các phần tử bằng 10 và mỗi phần tử là số nguyên tố.

Với truy vấn 2 (K = 4): Tương tự, đây là các mảng đối xứng có độ dài 4, tích các phần tử bằng 10 và mỗi phần tử là số nguyên tố.

Lưu ý:

• Hai mảng được coi là khác biệt nếu tồn tại ít nhất một vị trí mà giá trị phần tử ở hai mảng khác nhau
• Một mảng được gọi là đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau