PA06ANT - Ant

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 v1v2, 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 kp, 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 ≤ v1, v2 ≤ H, v1 ≠ v2.
* 1 ≤ k ≤ 2 x 109, 2 ≤ p ≤ 109.


Added by:AnhDQ
Date:2009-09-20
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:PA 2006 Round 5

hide comments
2022-03-18 08:27:36
One more test case:
A B
103 1000000007
160006305
2012-11-01 13:35:46 :D
Currently SPOJ runs all test cases and then checks them at the end. I don't know why, but that's how it is. You might as well got WA on all of them.
2012-10-31 21:26:57 Artur Laskowski
Could somebody tell me why my program get WA at 30 test?
I mean that my program pass 29 judges and then gets WA. My submition has number 7971312.
2012-08-27 17:00:04 Raghavendran Ramachandran
Are the edges birdirectional?
2009-09-22 21:46:45 hosam samy
What does that mean 1 ≤ k ≤ "2.10^9" ??

Re: it means 2 x 10^9 = 2,000,000,000; sorry, it may be different from some local education systems ^^


Last edit: 2009-09-22 14:15:03
2009-09-22 21:46:45 .:: Pratik ::.
The image is more than enough isnt it? Use the forums, i suggest.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.