689. Factorial of a Number

Given a non-negative integer N, compute and return N! (N factorial) using recursion. N! is defined as: N! = N × (N-1) × (N-2) × ... × 1, with 0! = 1 and 1! = 1. The result can be very large — return the exact integer value.

Input: A single non-negative integer N (0 ≤ N ≤ 70).

Output: A single integer — the factorial of N.

Examples

Input: 5
Output: 120
Explanation: 5! = 5×4×3×2×1 = 120. Recursion: fact(5)=5×fact(4)=5×24=120.

Input: 0
Output: 1
Explanation: Base case: 0! = 1 by definition.

Input: 10
Output: 3628800
Explanation: 10! = 10×9×8×...×1 = 3628800.

Constraints

• 0 <= N <= 20

Asked by