Nicholas must
deliver gifts to n (n ≤ 1018) children. He
wonders in how many ways he
can do it. You need to answer this simple question. Since this number may be
very large, print the result modulo m
(m ≤ 2009).
Input. Two positive integers n
and m.
Output. Print the
number of possible ways deliver presents.
|
Sample
input |
Sample
output |
|
5 1000 |
120 |
elementary
problem
Algorithm analysis
The number of ways to
deliver presents equals to n! mod m. If m ≤ n, then m is included as a factor in n!. In this case n! mod m = 0.
Otherwise (when n < m) calculate the value of
expression n! mod m with a loop. The number of iterations
is no more than n < m ≤ 2009.
Sample
100! mod 77 = (1 * 2 * … * 76 * 77 * 78 * … * 100) mod 77
= 0 because 100! is divisible by 77.
Algorithm realization
Read input data.
scanf("%lld %lld",&n,&m);
If m ≤ n, the answer is 0.
if (n >= m) res = 0; else
{
Otherwise n < m ≤ 2009, we find the value n! mod m using a loop.
for(res = i =
1; i <= n; i++)
res =
(res * i) % m;
}
Print the answer.
printf("%lld\n",res);
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
long n = con.nextLong();
long m = con.nextLong();
long res = 1;
if (n >= m) res = 0;
else
{
for(long i = 1; i <= n; i++)
res = (res * i) % m;
}
System.out.println(res);
con.close();
}
}
Python realization
n, m = map(int,input().split())
if n >= m: res = 0
else:
res = 1
for i in range (1, n+1):
res = (res * i) % m
print(res)