N! mod P (2)

Time limit3sMemory limit1024 MB

Summary
Given N and a prime P with N < P, compute N! modulo P.
Level

Easy3 of 10

Topics
Implementation, Math
Solved
No attempts yet

Problem

Given a positive integer N and a prime P greater than N, find the remainder of N! divided by P.

Input

The first line gives N and P separated by a space.

Output

Print the remainder of N! divided by P.

Constraints

  • 1 ≤ N < P ≤ 10^9
  • P is prime

Hint

The intended solution written by the problem setter runs in about 150ms.

Examples2

  1. Example 1

    Input
    4 7
    Expected output
    3

  2. Example 2

    Input
    999999936 999999937
    Expected output
    999999936