题目描述

小青在学习递归，他想用递归来计算阶乘。

n 的阶乘表示为 n! = 1 × 2 × 3 × ... × n

请你帮助小青用递归的方法计算阶乘。

输入格式

输入一个非负整数 n

输出格式

输出 n 的阶乘

样例

样例 1

输入 #1

5

输出 #1

120

样例 2

输入 #2

0

输出 #2

1

提示

递归公式：n! = n × (n-1)!，0! = 1