Liczby podzielne przez 3 - ciąg dalszy

Załóżmy, że rozpatrujemy liczby podzielne przez trzy. Rozpatrywana liczba może mieć niektóre cyfry przysłonięte znakiem gwiazdki. Dodatkowo wiadomo, że cyfry, które zostały przysłonięte zawierają się w pewnym zbiorze. Określ, ile może powstać w ten sposób liczb podzielnych przez 3, jeśli zamiast gwiazdki, możesz użyć cyfr, które zostały wcześniej zdefiniowane.

Wejście

W pierwszym wierszu jedna liczba c określająca liczbę cyfr, które możemy zastąpić za gwiazdki 0 < c < 11.

W drugim wierszu c cyfr systemu dziesiętnego. Każda cyfra wystąpi co najwyżej raz.

Następnie jedna liczba t określająca liczbę zestawów danych (t < 10001).

Każdy zestaw składa się z jednej liczby, maksymalnie 1000 znaków. Gwarantuje się, że najbardziej znacząca cyfra nie jest gwiazdką.

Wyjście

Dla każdego zestawu jedna liczba określająca liczbę liczb podzielnych przez 3. Wynik przedstaw modulo 1010101011.

Przykład

Wejście:
3
1 6 2
5
1
1*
111
3*
3***

Wyjście:
0
1
1
1
9

Szkic rozwiązania

W tym zadaniu należy zastosować podejście dynamiczne. Dla każdej gwiazdki spamiętujemy ile może powstać liczb, które dadzą nam resztę 0, 1 lub 2. Rozwiązaniem będzie liczba, która dla ostatniej gwiazdki będzie przechowywana dla reszty równej 0 uwzględniając sumę odkrytych cyfr.