Khi các em học sinh chuyên tin bắt đầu tìm hiểu và học về khái niệm đệ quy, hàm đệ quy, không ít bài viết và tài liệu đều lấy ví dụ “tính ~n~ giai thừa bằng hàm đệ quy”. ~n!~ (đọc là ~n~ giai thừa) là phép toán một ngôi trên tập hợp các số tự nhiên. ~n~ giai thừa là tích của ~n~ số nguyên dương đầu tiên, tức là: ~n! = 1 \times 2 \times 3 \times \dots \times n~. Từ công thức trên ta nhận ra rằng: ~n! = (n - 1)! \times n~.

Vì thế, nếu ta cài đặt hàm ~dq(n)~ để tính ~n!~, ta có thể cài đặt như sau:

int dq(int n){
    if (n == 0)
        return 1; // 0! = 1
    return dq(n - 1) * n; // n! = (n - 1)! * n
}

Sau khi đã hiểu và sử dụng thành thạo hàm đệ quy, một thời gian sau giáo viên sẽ cho các em tiếp cận kiến thức số học căn bản. Để tăng sự hứng thú cho học sinh, giáo viên quyết định cho các em làm một bài toán có liên quan đến hàm giai thừa vừa được học.

Yêu cầu: Cho hai số ~n~ và ~m~, hãy tính ~\lfloor \frac{n!}{m} \rfloor~. Trong đó ~\lfloor x \rfloor~ là số nguyên lớn nhất không vượt quá ~x~. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia ~\lfloor \frac{n!}{m} \rfloor~ cho ~(10^9 + 7)~.

Input

• Gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 10^6)~.

Output

• Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

1 2

Sample Output 1

0

Sample Input 2

4 2

Sample Output 2

12