Recursion: Factorial

Recursion: factorial n!

Compute n! (the factorial of n) recursively. n! = n × (n-1) × … × 2 × 1, with 0! = 1.

This is the same fact shown in the page's animation. Complete it, remembering recursion's two parts:

• Base case: when n == 0, return 1 directly (we have bottomed out; stop recursing).
• Recursive case: return n * fact(n - 1) (shrink the problem by 1 and hand it to a smaller copy of itself).

Pitfalls (straight from the bug lab): (1) omitting the base if (n == 0) return 1; causes infinite recursion and a stack overflow. (2) Returning 0 instead of 1 in the base makes the whole product collapse to 0 (the identity for multiplication is 1, not 0). (3) The recursive call must be fact(n - 1); dropping the -1 means n never shrinks and the base is never reached.

Input

• One line: integer n (0 ≤ n ≤ 12, the result fits in int).

Output

• One line: the value of n!.

Example: input 4 -> 24 (since 4×3×2×1 = 24).