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.


Được gửi lên bởi:AnhDQ
Ngày:2009-09-20
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:PA 2006 Round 5

hide comments
2021-05-27 18:02:50
Tham khảo: https://vnspoj.github.io/problems/PA06ANT
2021-01-23 11:04:02
:((
2018-06-15 18:05:00
code ac : https://ideone.com/pckN1D
2015-08-30 04:10:34
bài thốn vãi :((
2015-05-04 01:01:05 Stupid Dog
đề gốc với hình :

http://main.edu.pl/en/archive/pa/2006/mro
2013-03-15 14:51:56 Chế Quốc Hữu
Cho em hỏi bài này trên đường đi có được phép qua điểm kết thúc không ạ?
2012-01-01 05:19:04 Noyethug
hjx.chán quá k xem đc cái hình..:(
2009-09-27 04:09:39 HaiZ
neu k=6 thi co' dc dj nhu the' nay` khong
A B C D A B ...

Last edit: 2009-09-27 04:10:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.