(cards.*)

Bờm tham gia trò chơi rút thăm trúng thưởng trong đêm hội Trăng rằm. Ban tổ chức chuẩn bị \(k\) loại thẻ bài, các loại thẻ bài tương ứng ghi các giá trị từ \(1\) đến \(k\), các thẻ được sắp xếp vào trong 2 chiếc hộp như sau:

• Hộp thứ nhất: chỉ chứa các loại thẻ bài có giá trị là số lẻ trong đoạn từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.

• Hộp thứ hai: chỉ chứa các loại thẻ bài có giá trị là số chẵn trong đoạn từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.

Theo thể lệ của Ban tổ chức, một người chơi sẽ được thực hiện \(n\) lần rút thẻ. Các lượt rút thẻ theo thứ tự bắt đầu từ hộp thứ nhất tới hộp thứ hai và lặp lại quá trình đó.

Ví dụ: \(k = 4,\ n = 3\)

• Lượt thứ nhất: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị 1 hoặc 3.

• Lượt thứ hai: Người chơi rút thẻ trong hộp thứ hai có thể nhận được các thẻ bài có giá trị 2 hoặc 4.

• Lượt thứ ba: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị 1 hoặc 3.

Ban tổ chức đưa ra một con số \(m\) và người chơi sẽ nhận được quà nếu tổng giá trị các thẻ bài sau \(n\) lần rút là một số chia hết cho \(m\).

Yêu cầu: Hãy tính giúp Bờm xem có bao nhiêu cách rút ra các thẻ bài để có thể nhận được thưởng.

Dữ liệu: Vào từ tệp văn bản CARDS.INP

• Một dòng gồm ba số nguyên dương \(n,\ k,\ m\ \left( 2 \leq n,k \leq 10^{9},m \leq 100 \right)\)

Kết quả: Xuất ra tệp văn bản CARDS.OUT

• Một số nguyên dương là số cách rút thẻ thỏa mãn yêu cầu của Ban tổ chức. Vì kết quả rất lớn nên bạn chỉ cần đưa ra phần dư của đáp án khi chia cho 123456789.

Ví dụ:

Giải thích: Có tất cả 8 cách rút, nhưng có 4 cách rút thẻ có tổng chia hết cho 4:

Cách 1: 1 2 1

Cách 2: 1 4 3

Cách 3: 3 4 1

Cách 4: 3 2 3

Ràng buộc:

• Có 20% số điểm với \(n,k \leq \ 1000\)

• Có 30% số điểm khác với \(m\) lẻ, \(n \leq 1000\)

• Có 30% số điểm khác thỏa mãn \(n \leq 1000\)

• Còn lại không có điều kiện gì thêm.