#42Easy

Sum of factorials

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given a natural number $n$ . Find $1! + 2! + \ldots + n!$ , where $k! = 1 \cdot 2 \cdot \ldots \cdot k$ .

Input format

A single integer $n$ ( $1 \le n \le 20$ ).

Output format

A single integer — the sum.

Examples

Input

Output

Input

Output

Note

You do not need to compute each factorial from scratch: $k! = (k - 1)! \cdot k$ . Update the current factorial inside one loop and add it to the sum.

$20! \approx 2.4 \cdot 10^{18}$ , and already $13!$ does not fit into 32 bits. Use long long in C++ and int64 in Go. In the first example: $1 + 2 + 6 + 24 = 33$ .

Sum of factorials

Time: 1 s · Memory: 256 MB

Loops

Statement

You are given a natural number $n$ . Find $1! + 2! + \ldots + n!$ , where $k! = 1 \cdot 2 \cdot \ldots \cdot k$ .

Input format

A single integer $n$ ( $1 \le n \le 20$ ).

Output format

A single integer — the sum.

Examples

Input

Output

Input

Output

Note

You do not need to compute each factorial from scratch: $k! = (k - 1)! \cdot k$ . Update the current factorial inside one loop and add it to the sum.

$20! \approx 2.4 \cdot 10^{18}$ , and already $13!$ does not fit into 32 bits. Use long long in C++ and int64 in Go. In the first example: $1 + 2 + 6 + 24 = 33$ .