Fermat's Little Theorem


Plus
Pin


Problem description Progress
ID 31866. Application of Fermat's Little Theorem
Темы: Fermat's Little Theorem   

Given a number a and a prime number p. Find the minimum number x such that \((a * x) \% p = 1\).


Input
The input is two natural numbers ap (\(a,\ p <= 10^ {18} \)).

Imprint
Print the answer to the problem.
 

 

Examples
# Input Output
1 2 5 3
 

ID 30699. Gangs of Fomin No. 2
Темы: Prefix sums(minimums, ...)    Fermat's Little Theorem    Remains    Fast exponentiation   

Fomin's gang consists of n groups, each of which has ai people. q raids are planned. The i-th raid will include exactly one robber from each group whose number lies in the segment \([l_i, r_i]\).

Melekhov is sad, so for each raid he decided to calculate the number of possible units modulo \(10^9 + 7\). However, Gregory is constantly thinking about the meaning of life and searching for the truth, so he cannot concentrate on calculations and asks you for help.

Input
The first line contains the number n (\(1 <= n <= 10^5\)) – the number of groups in Fomin's gang.
The second line contains n natural numbers ai (\(1 <= a_i < = 10^6\)) – the number of people in the i-th group.
The third line contains the number q – number of raids.
The following are q lines, each containing two numbers – li and ri (\(1 <= l_i <= r_i <= n\)) – numbers of groups participating in i-th raid.

Imprint
Print q numbers, each on a separate line – response to the task.

 

Examples
# Input Output
1 6
1 3 7 1 4 100
3
1 3
34
26
21
7
8400