Một chiếc cầu thang có n bậc, một người nào đó có thể bước một bước lên một, hai hoặc ba bậc. Hỏi để lên hết n bậc thang thì người đó có bao nhiêu cách leo thang

Input

Một số nguyên dương 1<=n<=20

Output

Một số nguyên dương là số cách lên n bậc thang

Example

Input

4

Output

7

Giải thích: Có thể có các cách lên sau

Cách 1: 1+1+1+1 (Bước từng bậc)

Cách 2: 2+1+1 (Bước đầu 2 bậc sau đó là từng bậc)

Cách 3: 1+2+1

Cách 4: 1+1+2

Cách 5: 1+3

Cách 6: 3+1

Cách 7: 2+2