Trong giờ học Toán, hai bạn Kina và Luna đang ngồi chơi caro thì bị thầy Tina bắt gặp. Thấy hai bạn đang vẽ sẵn một bảng vuông ~n \times n~ nên thầy bèn ra luôn một đề bài như sau: cho hai số nguyên dương ~a, m~ trong đó ~a~ chia hết cho ~m~, hỏi có bao nhiêu cách điền các số nguyên từ ~1 \to a~ vào bảng, mỗi số một ô sao cho tổng các số trên mỗi hàng và mỗi cột đều chia hết cho ~m~?

Hai bạn đã tính ra kết quả nhưng vì giá trị quá lớn nên đã xin phép thầy Tina là lấy mod ~19741991~ (là năm sinh của hai bạn ghép lại), bây giờ mọi người thử cùng trải nghiệm bài toán vui này nhé.

Thầy Tina sau khi thấy hai bạn giải khá lâu mà chưa ra nên đã có chút gợi ý: "hãy chú ý vào hình vuông con ~(n-1) \times (n-1)~ ở góc trên bên trái."

Input: một dòng duy nhất gồm ba số nguyên dương ~n, m, a~ với ~2 \le n, m, a \le 10^9~, cho biết rằng ~a~ chia hết cho ~m~.

Output: đáp số của bài toán, lấy modulo ~19741991.~

Sample input 1:

2 2 2

Sample output 1:

2

Sample input 2:

2023 5 15

Sample output 2:

6854631

Giải thích:

Ở ví dụ 1, ta liệt kê được hai bảng full số 1 và full số 2.