7441. Factorial

 

Input. One integer n (1 ≤ n ≤ 1018).

 

Output. Print n! (mod 3469708049238200000).

 

Sample input

Sample output

6

720

 

 

SOLUTION

mathematics

 

Algorithm analysis

Notice that 3469708049238200000 = 26 * 55 * 79 * 113 * 17 * 19. As soon as the factorization of n! contains all the factors from the set {26, 55, 79, 113, 17, 19}, then n! (mod 3469708049238200000) = 0. The smallest number that satisfies this condition will be n = 56. Number 55! is divisible by 78 but not divisible by 79. So the answer is 0 for n ≥ 56.

For C / C++, the unsigned long long type is not enough to avoid overflow. Use Java or Python.

 

Algorithm realization

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    long n = con.nextLong();

    BigInteger res = BigInteger.ONE;

    BigInteger MOD = new BigInteger("3469708049238200000");

 

    for (int i = 1; i <= n; i++)

    {

      res = res.multiply(BigInteger.valueOf(i)).mod(MOD);

      if (res == BigInteger.ZERO) break;

    }

 

    System.out.println(res);

    con.close();

  }

}