题目描述

将正整数n表示成一系列正整数之和：$n=n_1+n_2+ \dots +n_k$，其中$8>=n_1 >= n_2 >= \dots n_k >=1$，k≥1。正整数n的这种表示称为正整数n的划分。

例如正整数6有如下11种不同的划分：

6；
5+1；
4+2，  4+1+1；
3+3，  3+2+1，  3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。

输入格式

一个正整数 n 保证 n<=8

输出格式

一个正整数 m，表示n可以被分成m种

样例

input

6

output

11

限制与提示

时间限制：1s

空间限制：256MB