Skip to content

Large Factorial Modulo M

easy Math and Number Theory

Read n and m. Print n! mod m. The factorial is huge, so take the remainder after every multiplication.

Constraints

0 <= n <= 10^6
1 <= m <= 10^9

Examples

Input

5 7

Output

Modular arithmetic
Overflow control

Solutions

Best approachTime O(n)Space O(1)

(x * y) mod m = ((x mod m) * (y mod m)) mod m. So we can reduce after each step and never build the huge factorial.

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Compute n! mod m.
 * Input   : Two integers n and m.
 * Output  : n! mod m.
 * Approach: Take mod after each multiplication.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long a, long b) {
        // Step 1: The result starts at 1 mod m (this is 0 when m is 1).
        long result = 1 % b;

        // Step 2: Multiply by 2, 3, ..., n. Take the remainder each time, so the number never gets too big.
        for (long i = 2; i <= a; i++) {
            result = result * i % b;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}

Hints (1)

Does the remainder of a product depend only on the remainders of the factors?