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\).

Input

• Gồm một dòng chứa đỉnh xuất phát và đỉnh kết thúc trên hành trình của chú kiến các đỉnh được kí hiệu bằng các chữ cái in hoa ABCDEFGH, hai số \(k\) và \(p\) \((k \le 2 \times 10^9, p \le 10^9)\).

Output

• Một số nguyên duy nhất là đáp án.

Example

A B 3 100

2