Medicine

Time limit1sMemory limit512 MB

Summary

Count the ways to remove 3N packets from either end when the morning and evening packets are interchangeable but the noon packet is fixed.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Recursion, Math
Solved: No attempts yet

Problem

Jun must take medicine for $N$ days. The medicine is taken once in the morning, once at noon, and once in the evening, and each dose is packed in a packet. The $3N$ packets are attached in a row, formed by concatenating {(morning medicine), (noon medicine), (evening medicine)} $N$ times. When taking medicine, only the frontmost packet and the backmost packet can be torn off and taken.

Because the morning medicine and the evening medicine are the same, one may take the evening medicine in the morning and the morning medicine in the evening. However, the noon medicine must be taken only at noon. For this reason, methods other than taking the packets in order from the front also exist.

Given $N$ , find the number of distinct ways to take the medicine.

Input

The first line gives $N$ .

Output

Print the number of distinct ways to take $N$ days' worth of medicine.

Constraints

$1 \le N \le 15$

Examples2

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
6
```