Algorithm

Problem link- https://www.spoj.com/problems/DCEPC11B/

DCEPC11B - Boring Factorials

#math

 

Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend has been helping them out. But as it goes, Sameer and Arpit have got bored of problems involving factorials. Reason being, the factorials are too easy to calculate in problems as they only require the residue modulo some prime and that is easy to calculate in linear time. So to make things interesting for them, Aman - The Mathemagician, gives them an interesting task. He gives them a prime number P and an integer N close to P, and asks them to find N! modulo P. He asks T such queries.

Input

First line contains an integer T, the number of queries asked.

Next T lines contains T queries of the form “N P”. (quotes for clarity)

Output

Output exactly T lines, containing N! modulo P.

Example

Input:
3
2 5
5 11
21 71

Output:
2
10
6

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

def power(a, b, modulo):
    if b == 0:
        return 1 % modulo
    if b % 2 == 1:
        return power(a, b - 1, modulo) * a % modulo
    half = power(a, b >> 1, modulo)
    return half * half % modulo
def solve(a, b):
    product = 1
    for i in range(a + 1, b):
        product = product * i % b
    return (b - 1) * power(product, b - 2, b) % b
T = int(input())
for i in range(T):
    (N, P) = map(int, raw_input().split())
    if N >= P:
        print(0)
    else:
        print(solve(N, P))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
2 5
5 11
21 71

Output

x
–
+
cmd
2
10
6
Advertisements

Demonstration

SPOJ Solution-Boring Factorials-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python