I helped run a local high school contest earlier this year. For the last problem of the practice contest, I wanted to write a meme problem that was ridiculously "hard" (really just a knowledge check that's not appropriate for the participants, but would stimulate some conversation among them before the actual contest). I did not know it at the time, but this is actually similar to (albeit a bit easier than) a previous problem: 1103E - Radix sum

If anyone wants to try it, here is what it was:

Finally, Fouring Time!

You've just received a phone call from Dr. Phoughrierre! The mad doctor tells you that he's currently on the surface of a rather high-dimensional torus. He said something unintelligible along the lines of ''they can't catch me here on $$$(\mathbb{R}/4\mathbb{Z})^n$$$.'' You're not sure what that means, but you know that you were supposed to be practicing dancing with him right about now.

Luckily, you're in space that has the same number of dimensions $$$n$$$ as Dr. Phoughrierre, so you can just practice your dances remotely with him! However, while you can move any distance in any direction at any time, Dr. Phoughrierre loops back around whenever he steps 4 units along any of the coordinate axes. Since you don't want him to get lost, right now you can only practice dances that take him back to where he started. A ''dance move'' is a sequence of $$$n$$$ integers between 0 and 3, corresponding to the amount of distance moved along each of the $$$n$$$ coordinate axes. A ''dance'' is a sequence of $$$k$$$ dance moves corresponding to the steps in the routine. Two dances are considered different if any of their moves is different.

Input

The first line will consist of three space-separated integers: the number of dimensions $$$n$$$ ($$$1 \leq n \leq 10$$$), the number of known dance moves $$$d$$$ ($$$1 \leq d \leq 4^n$$$), and the number of moves in a dance $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$).

The next $$$d$$$ lines contain one dance move each. A dance move is written as a sequence of $$$n$$$ digits from 0 through 3. All known dance moves are guaranteed to be distinct.

Output

Let $$$D$$$ be the number of dances of length $$$k$$$ that do not displace Dr. Phoughrierre. Since $$$D$$$ can be quite large, print on one line the remainder when $$$D$$$ is divided by $$$999\,999\,937$$$.

Samples

Sample input 1

3 4 2
202
022
220
111

Sample output 1

3

Sample input 2

3 4 3
202
022
220
111

Sample output 2

6

Sample input 3

1 1 1
3

Sample output 3

0

Sample input 4

1 2 1000
2
0

Sample output 4

128930244

It is not impossible that I did not copy the samples/formatting correctly into codeforces, so please let me know if there are any glaring errors.

I will spare you folks the image of a trollface stick figure walking on a torus that was present in the actual PDF of the problem.

Also, I will have to write a quick solution guide for this soon anyway, so I will update this post when that is done.