402861: GYM100923 E Por Costel and the Cipher

Por Costel the pig has found a legendary safe. It is said that it "holds so much food that a man may feast on it for countless years". He thinks it might be enough for breakfast.

However, he must first bypass its security mechanism which is very similar(surprisingly) to that of a suitcase.

In order to open the safe, one must insert a code of length ( digits from to ). The code is inserted by the means of small wheels. These can be turned upward or downward. If a wheel indicates value , it can be moved upward to indicate value mod , or it can be moved downward to indicate value mod .

The legend says that the safe was crafted by elder pigs. That is why there exist distinct codes that open the safe. Also, the safe has deteriorated with the passing of time and now every wheel has an "error margin" given by a number . This means that a code will open the safe if there exists at least one code out of th elder pig codes such that for any in the range , where

means the minimum number of wheel turns in order to get from digit to digit

means the -th digit of code .

Given that the system was designed by pigs, it was to be expected that it's not top-notch. There are many codes that open the safe. SO many in fact, that if one were to count them, he would have to do so mod . Calculate this value! Por Costel can't hold his appetite much longer!

The input file cifrul.in will contain on its first line an integer (), the number of tests. On the following lines, each test will be described by the following:

The first line of a test case contains four integer numbers (), (), and ().

The next lines will each contain integer numbers. These will be the codes of the elder pigs. The -th line describes the -th code.

Print lines in the file cifrul.out. The -th line should contain the answer for the -th test case.

2
1 2 10000 3
1
6
3 1 100 5
1 6 30

12
1331