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é.

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.