github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: KOL1501
problem_name: 'In a planet far far away'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: devuy11
problem_tester: null
date_added: 28-11-2015
tags:
    - acm15kol
    - devuy11
    - dynamic
    - long
    - multiplication
editorial_url: 'http://discuss.codechef.com/problems/KOL1501'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493557717
layout: problem
---
All submissions for this problem are available.CodeChef has sent Jalebi Bai to a new planet to learn a special recipe from them. On her journey from the space station to the head chef's house, she observed that the multiplication rule on this new planet is slightly different from our Earth.

For example: on this planet, 2\*4 may be 9 instead of 8. Weird, she thought.

Curious, Jalebi Bai asked a co-passenger the results of all the 100 multiplications between all pairs of digits.

She figured out that the Standard algorithm for multiplication on this planet follows the same rules as on Earth except that digit multiplication should follow the rule of that planet.

She also found out that any digit multiplied with 0 is 0, the multiplication of x with y is the same as the multiplication of y with x.

Addition is defined to be same as that on the Earth.

For example, if the result of 2 multiplied with 4 is 9, 5 multiplied with 3 is 19, 2 multiplied with 3 is 17 and 4 multiplied with 5 is 24, then multiplication of 25 with 43 will give:

<pre><tt>
			  25
			  43
		---------------
			  19
			 170
			 240
			 900
		---------------
			1329
		---------------
</tt>
</pre>The final answer will be 1329 (following the addition algorithm of the earth for managing carry).

Finally Jalebi Bai meets the head chef of the planet, but the problem is he is ready to give her the recipe only if she can solve a puzzle. He asks her to find the sum of the results of multiplication (according to the planet) between all possible ordered pairs of numbers from the set of positive integer less than or equal to a given number **A**. **Note:** If **i** and **j** are distinct, then the pair (**i**,**j**) is considered different from (**j**,**i**).

Jalebi Bai then asks him for a formal multiplication algorithm of the planet, to which the head chef agrees and gives following description.

The multiplication of two numbers **X** and **Y** represented as arrays, with **M** as the digit multiplication matrix, is defined as follows:

<pre><tt>
Multiply(X[1..p], Y[1..q])
{
    m = [1..p+q]  //Allocate space for result
    for b = 1 to q
    {
        carry = 0
        for a = 1 to p
        {
            m[a + b - 1] += carry + M[X[a]] [Y[b]]
            carry = m[a + b - 1] /10
            m[a + b - 1] = m[a + b - 1] mod 10
        }
        m[b + p] += carry
    }
    answer = 0
    for r = p+q to 1
        answer = answer*10 + m[r]
    return answer
}
</tt>
</pre>Aliens cannot hear any large number, so they want to hear the output modulo **Mod**, where **Mod** is some integer.

If Jalebi Bai gives a wrong output, she would be eaten up! (Surprise surprise!)

Jalebi Bai can contact someone on earth for help. She reaches you for a code which can evaluate the output for any given input. Can you help her solve this puzzle?

### Input

The digit multiplication rule appears in 9 lines. Line **i** contains the multiplication rule for the digit **i**. Each line contains **9** positive integers, each of which is less than **100**. It is guaranteed that the given matrix is symmetric.

The next line contains **T**, the number of test cases to evaluate.

The first line of each test case contains a positive integer **A**.

The second line of each test case contains **Mod**.

### Output

For each test case, output the solution modulo **Mod** in a single line.

### Constraints

- **1** ≤ **T** ≤ **50000**
- **1** ≤ **A** < **10100000**
- **1** ≤ **Mod** ≤ **108**
- **1** ≤ **Sum of lengths of all strings A** ≤ **5\*105**

### Example1

<pre><b>Input:</b>
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81
3
9
10000
73
100
83
100
<b>Output:</b>
2025
1
96
</pre>### Example2

<pre><b>Input:</b>
1 1 1 1 1 1 1 1 1
1 4 6 8 10 12 14 16 18
1 6 9 12 15 18 21 24 27
1 8 12 16 20 24 28 32 36
1 10 15 20 25 30 35 40 45
1 12 18 24 30 36 42 48 54
1 14 21 28 35 42 49 56 63
1 16 24 32 40 48 56 64 72
1 18 27 36 45 54 63 72 81
1
9
10000

<b>Output:</b>
1953
</pre>### Explanation

**Example case 1.** Normal multiplication rule follows.

**Example case 2.** The only pairs with multiplication different from normal multiplication are (1, 2), (1, 3), ..., (1, 9) and (2, 1), (3, 1), ..., (9, 1).