Plankan

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ordered ways to write a length n as a sum of parts 1, 2, and 3, where the order of boards matters.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Someone wants to build a longer plank out of smaller boards. There are three types of boards, with lengths 1, 2, and 3 meters. Each type is available in unlimited quantity.

There are $7$ ways to glue together a plank that is $4$ meters long.

Write a program that finds the number of different ways to make a plank of length $n$ .

Input

The first and only line contains an integer $n$ ( $1 \le n \le 24$ ), the length of the new plank.

Output

Print a single integer, the number of ways to glue together a plank that is $n$ meters long.

Examples1

Example 1
Input
```
4
```
Expected output
```
7
```