Giải bài trực tuyến

Một chú kiến dạo chơi trên một hình lập phương ABCDEFGH được mô tả dưới đây:

Chú kiến muốn biết rằng có bao nhiêu con đường để đi từ một đỉnh tới một đỉnh khác cho trước, đi qua đúng k cạnh (chú kiến luôn đi hết đoạn đường từ đầu này sang đầu kia một cạnh). Nếu chú kiến đi qua một cạnh x lần, ta đếm cạnh đó x lần. Chú muốn có một hành trình thú vị, vậy nên tại mỗi bước chú sẽ không đi lại đỉnh mà mình đã thăm ở bước ngay trước đó.

Chú kiến của chúng ta không được thông minh cho lắm, chú chỉ sử dụng được các số từ 0 tới p-1, vậy nên bạn cần tính toán kết quả theo modulo p.

Yêu cầu

Hãy viết một chương trình thực hiện các công việc sau:
* đọc đỉnh xuất phát và đỉnh kết thúc trên hành trình của chú kiến, số lượng cạnh chú kiến muốn đi qua và một số p,
* tính toán số lượng hành trình thú vị thỏa mãn các yêu cầu của chú kiến, theo modulo p,
* ghi đáp án ra output chuẩn.

Dữ liệu

Dòng đầu tiên của input chuẩn chứa hai chữ cái in hoa v₁ và v₂, cách nhau bởi một dấu cách trống. Hai chữ cái này lần lượt thể hiện đỉnh xuất phát và đỉnh kết thúc trên hành trình của chú kiến. Dòng thứ hai chứa hai số nguyên k và p, cách nhau bởi một dấu cách trống.

Kết quả

Ghi ra output chuẩn một số nguyên duy nhất là đáp án.

Ví dụ

Dữ liệu:
A B
3 100

Kết quả:
2

Giới hạn

* A ≤ v₁, v₂ ≤ H, v₁ ≠ v₂.
* 1 ≤ k ≤ 2 x 10⁹, 2 ≤ p ≤ 10⁹.