Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from *k* - 1 rocks, possesses power *p* and we want to add the rock charged with power *w*<sub class="lower-index">*k*</sub> then value of power of a new tower will be {*w*<sub class="lower-index">*k*</sub>}<sup class="upper-index">*p*</sup>. 

Rocks are added from the last to the first. That is for sequence *w*<sub class="lower-index">1</sub>, ..., *w*<sub class="lower-index">*m*</sub> value of power will be

After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo *m*. Priests have *n* rocks numbered from 1 to *n*. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered *l*, *l* + 1, ..., *r*.
First line of input contains two integers *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) and *m* (1 ≤ *m* ≤ 10<sup class="upper-index">9</sup>).

Second line of input contains *n* integers *w*<sub class="lower-index">*k*</sub> (1 ≤ *w*<sub class="lower-index">*k*</sub> ≤ 10<sup class="upper-index">9</sup>) which is the power of rocks that priests have.

Third line of input contains single integer *q* (1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>) which is amount of queries from priests to you.

*k*<sup class="upper-index">*th*</sup> of next *q* lines contains two integers *l*<sub class="lower-index">*k*</sub> and *r*<sub class="lower-index">*k*</sub> (1 ≤ *l*<sub class="lower-index">*k*</sub> ≤ *r*<sub class="lower-index">*k*</sub> ≤ *n*).
3<sup class="upper-index">27</sup> = 7625597484987
6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6
1
1
2
4
256
3
27
597484987
10 20
792708224 4633945 600798790 384332600 283309209 762285205 750900274 160512987 390669628 205259431
10
5 9
10 10
8 10
7 10
7 10
10 10
4 4
10 10
7 7
4 8
9
11
1
4
4
11
0
11
14
0
10 18634
157997476 953632869 382859292 108314887 739258690 110965928 172586126 28393671 86410659 427585718
10
8 10
6 10
5 10
1 5
10 10
2 5
9 9
7 10
10 10
7 8
15189
1038
6792
3640
9954
18165
4801
10646
9954
7258
10 50836233
851634701 930436567 638750681 245433831 713210442 596964772 755991944 672347390 511061574 910341009
10
2 7
6 8
5 8
9 10
2 6
1 10
7 9
5 9
7 7
1 9
12393313
39557380
49292502
46903641
12393313
7141667
33887764
49292502
44284682
7141667
10 1
688064407 427303738 659797188 392572027 589349296 634815051 224079967 887153080 734271558 734494149
10
6 6
3 5
1 8
3 6
3 10
4 7
8 10
8 8
8 8
10 10
0
0
0
0
0
0
0
0
0
0
10 2
955038141 449680214 399763026 876295481 481249362 481742997 44362794 989248781 543311754 393585591
10
10 10
7 10
7 9
5 5
8 10
7 10
9 9
2 9
1 1
2 5
1
0
0
0
1
0
0
0
1
0
10 1000000000
641599168 361387653 420063230 331976084 135516559 581380892 330923930 354835866 161468011 903819305
10
5 7
3 4
6 9
8 8
9 9
10 10
2 4
1 10
8 10
9 9
566300161
0
787109376
354835866
161468011
903819305
1
766599168
508591616
161468011
10 13
26 81 5 48 77 72 64 31 64 64
10
2 9
3 6
6 10
3 9
3 3
10 10
6 9
7 8
7 9
7 7
3
1
9
1
5
12
9
12
12
12
10 11626
75 62 33 89 15 23 79 44 42 64
10
3 10
8 9
4 6
1 3
8 9
2 7
10 10
4 8
4 4
9 10
9537
4034
1353
6273
4034
4810
64
475
89
1090
10 493276887
45 69 40 89 90 36 66 45 80 79
10
6 8
7 10
9 10
2 4
3 3
4 10
6 10
2 6
1 9
7 8
9246240
133793487
168548840
347974281
40
335479897
429073974
253420560
465717924
439476282
10 1
90 2 82 24 22 84 7 7 71 96
10
5 7
2 9
5 5
9 10
1 2
10 10
2 4
7 8
4 8
2 7
0
0
0
0
0
0
0
0
0
0
10 2
82 24 48 92 69 79 34 61 22 51
10
7 9
3 8
10 10
6 10
4 10
7 10
2 2
7 10
9 10
4 7
0
0
1
1
0
0
0
0
0
0
10 1000000000
38 41 74 34 75 43 34 67 80 61
10
3 9
3 8
3 4
8 9
3 3
5 5
10 10
6 10
8 9
10 10
678552576
678552576
570840576
371278401
74
75
61
683084801
371278401
61
10 17
3 1 4 3 2 3 2 4 1 2
10
8 10
3 6
10 10
2 4
2 9
2 4
10 10
10 10
1 6
8 9
4
4
2
1
1
1
2
2
3
4
10 16228
2 1 1 3 2 1 1 3 2 4
10
8 10
2 5
9 10
8 9
3 4
5 7
1 3
6 6
8 10
2 8
10065
1
16
9
1
2
2
1
10065
1
10 544434102
1 4 4 2 3 1 1 2 3 2
10
3 9
8 10
8 8
10 10
1 10
4 9
3 8
2 7
10 10
10 10
65536
512
2
2
1
8
65536
127776064
2
2
10 1
2 1 1 4 2 1 2 3 4 1
10
6 8
9 9
10 10
9 9
10 10
3 7
5 7
5 5
9 9
1 6
0
0
0
0
0
0
0
0
0
0
10 2
2 1 3 2 2 3 1 2 2 4
10
5 7
9 10
6 8
8 10
10 10
3 10
8 10
2 7
9 10
10 10
0
0
1
0
0
1
0
1
0
0
10 1000000000
1 1 4 4 4 1 1 2 1 2
10
3 7
3 9
2 5
3 9
1 9
7 10
5 10
3 9
5 5
10 10
6084096
6084096
1
6084096
1
1
4
6084096
4
2
10 17
3 1 4 3 2 3 2 4 1 2
10
8 10
3 4
10 10
2 2
2 4
2 5
10 10
10 10
1 1
8 9
4
13
2
1
1
1
2
2
3
4
10 16228
2 1 1 3 2 1 1 3 2 4
10
8 10
2 6
9 10
8 9
3 4
5 8
1 3
6 6
8 10
2 6
10065
1
16
9
1
2
2
1
10065
1
10 544434102
1 4 4 2 3 1 1 2 3 2
10
3 3
8 10
8 8
10 10
1 5
4 7
3 4
2 5
10 10
10 10
4
512
2
2
1
8
16
127776064
2
2
10 1
2 1 1 4 2 1 2 3 4 1
10
6 8
9 9
10 10
9 9
10 10
3 7
5 9
5 9
9 9
1 1
0
0
0
0
0
0
0
0
0
0
10 2
2 1 3 2 2 3 1 2 2 4
10
5 8
9 10
6 8
8 10
10 10
3 6
8 10
2 4
9 10
10 10
0
0
1
0
0
1
0
1
0
0
10 1000000000
1 1 4 4 4 1 1 2 1 2
10
3 6
3 5
2 2
3 3
1 4
7 10
5 8
3 4
5 6
10 10
6084096
6084096
1
4
1
1
4
256
4
2
10 20
792708224 4633945 600798790 384332600 283309209 762285205 750900274 160512987 390669628 205259431
10
5 9
10 10
8 10
7 10
7 10
10 10
4 6
10 10
7 7
4 5
9
11
1
4
4
11
0
11
14
0
10 18634
157997476 953632869 382859292 108314887 739258690 110965928 172586126 28393671 86410659 427585718
10
8 10
6 10
5 7
1 5
10 10
2 4
9 9
7 10
10 10
7 8
15189
1038
8556
3640
9954
2093
4801
10646
9954
7258
10 50836233
851634701 930436567 638750681 245433831 713210442 596964772 755991944 672347390 511061574 910341009
10
2 3
6 8
5 7
9 10
2 4
1 5
7 9
5 6
7 7
1 4
50678308
39557380
29895264
46903641
9930496
7141667
33887764
3470796
44284682
7141667
10 1
688064407 427303738 659797188 392572027 589349296 634815051 224079967 887153080 734271558 734494149
10
6 6
3 5
1 3
3 4
3 7
4 8
8 10
8 8
8 8
10 10
0
0
0
0
0
0
0
0
0
0
10 2
955038141 449680214 399763026 876295481 481249362 481742997 44362794 989248781 543311754 393585591
10
10 10
7 10
7 9
5 6
8 10
7 10
9 9
2 3
1 1
2 5
1
0
0
0
1
0
0
0
1
0
10 1000000000
641599168 361387653 420063230 331976084 135516559 581380892 330923930 354835866 161468011 903819305
10
5 8
3 7
6 9
8 8
9 9
10 10
2 4
1 5
8 10
9 9
20733441
0
787109376
354835866
161468011
903819305
1
766599168
508591616
161468011
MOD = 10**9 + 7

def pow( a, b, mod ):

    ret = 1

    while b > 0:

        if b & 1:
            ret = ( ret * a ) % mod

        a = ( a * a ) % mod

        b //= 2

    return ( ret )

def phi( n ):

    ans = n

    i = 2

    while i * i <= n:

        if n % i == 0:
            ans -= ans//i

        while n % i == 0:
            n //= i;

        i += 1

    if n != 1:
        ans -= ans // n

    return ( ans )

x = MOD

P = []

while True:
    x = phi(x)
    P.append(x)
    if x == 1:
        break

n, m = list( map( int, input().split() ) )
w = list( map( int, input().split() ) )

q = int( input() )

def solve( left, right, who ):

    if left == right:
        return w[left] % P[who]

    ret = w[left]

    cnt = 0

    ret = pow( w[left], solve(left+1,right,who+1), P[who] )

    return ( ret )

for i in range(q):
    l, r = list( map( int, input().split() ) )
    print( solve(l-1,r-1, 0) )

#for i in range( 0, 28 ):
#    print( str(i) + " " + str( pow(3,i) ) )
