Counting Stars

All submissions for this problem are available.
In a galaxy far away, space is Ddimensional and folds like donuts. There are K types of stars in the galaxy. The stars are arranged in an M x M x M ... X M (D times) hypercube, where M = 3^N. Thus, there are 3^(N*D) stars. You will be given N to specify M.
As we said, space folds like donuts. Let's see what that means.
There are D dimensions, named from 1 ... D. Stars in a row along dimension 1 (with the same coordinates in dimensions 2 ... D) can rotate in the following manner. The first star in the row, can go to the second position, the second to the third, the last to the first, and so on. These 'rotations' take place freely without constraint, and the stars retain their original coordinates in the other D1 dimensions.
Let's say the stars have types from 1 ... K. Now, two configurations of stars in a row in the first dimension are considered equivalent if through such rotations described above, we can reach the second configuration from the first.
However, this is not it. Space twists like donuts, in all dimensions. Precisely, the following can happen. Consider rows in the first dimension stacked along the second dimension (to form a planar structure). These rows of configurations can rotate freely along this second dimension, much in the same way as single stars rotate along a row. However, in this case, a single star cannot move along the second dimension without it's neighbors in the first dimension.
Now consider a stacking of planes of the second dimension to form a cube in the third dimension. The planes can rotate along this cube, similar to what is described above. Again, planes move along with it's neighbors. In general, a structure in the first k dimensions of size M X M X .. M (k times) can rotate around in the (k+1)'th dimension.
As described above, two configurations in these D dimensions are considered equivalent if one can be obtained from the other by such rotations. Your task is to output the possible number of nonequivalent configurations, modulo an odd prime P of the form 3k + 2.
As an illustrative example in 2D, with 2 types of stars, consider the following three equivalent configurations.
110 001 010
is converted to the following by picking the top row and put it at the bottom, shifting rows 2 and 3 upwards 
001 010 110
This configuration is converted to the following configuration by rotating the bottom and the top rows by 1 to the left. The middle row is untouched.
010 010 101
The following is a configuration that cannot be reached.
010 111 000Input
There is single test case, containing 4 space separated numbers, P, N, K, D.
Output
Output a single integer, the possible number of nonequivalent configurations.
Constraints
 2 ≤ N ≤ 10^12
 5 ≤ P ≤ 10^3
 P is an odd prime of the form 3k + 2
 1 ≤ D ≤ 50
 2 ≤ K ≤ 10^4
Example
Input: 5 3 2 2 Output: 2
Author:  triveni 
Tags  triveni 
Date Added:  10032015 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 