PA06ANT  Ant
English  Tiếng Việt 
A Byteotian ant is walking along the edges of ABCDEFGH cube:
It tries to find out, in how many ways it can go from one given vertex, to another given vertex, walking along exactly k edges (when the ant enters an edge, it will not turn back and will finally reach the second end of this edge). If the ant goes through some edge x times, we count this edge x times. The ant would like to have interesting routes, that is if the ant is in some vertex, it would like to leave this vertex using an edge other than the edge recently used to enter this vertex (i.e. it want not to use the same edge twice in a row).
Our ant is not so smart, because it can only count using integers from 0 to p1, for some p, so you should compute the result modulo p.
Request
Write a program which:
* reads the starting and the ending vertex of the ant's route, number of edges on the ant's route, and integer p,
* computes number of interesting routes, which satisfy the ant's requests, modulo p,
* writes the answer to the standard output.
Input
The first line of the standard input contains two capital English letters v_{1} and v_{2}, separated by a single space. The two letters denote the starting and ending vertex of the ant's route respectively. The second line contains two integers k and p, separated by a single space.
Output
Exactly one integer is to be written on the standard output. This integer is the number of interesting routes from the vertex v_{1} to the vertex v_{2}, containing exactly k edges, modulo p.
Example
Input: A B 3 100 Output: 2
Limitations
* A ≤ v_{1}, v_{2} ≤ H, v_{1} ≠ v_{2}.
* 1 ≤ k ≤ 2 x 10^{9}, 2 ≤ p ≤ 10^{9}.
hide comments
smso:
20220318 08:27:36
One more test case:


:D:
20121101 13:35:46
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. 

Artur Laskowski:
20121031 21:26:57
Could somebody tell me why my program get WA at 30 test?


Raghavendran Ramachandran:
20120827 17:00:04
Are the edges birdirectional? 

hosam samy:
20090922 21:46:45
What does that mean 1 ≤ k ≤ "2.10^9" ??


.:: Pratik ::.:
20090922 21:46:45
The image is more than enough isnt it? Use the forums, i suggest. 
Added by:  AnhDQ 
Date:  20090920 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  PA 2006 Round 5 