题目描述

给定一个正整数 $n$，求将 $n$ 拆分成 $1,3,4$ 之和的不同方案总数。

输入格式

一个正整数 $n$。

输出格式

一个正整数，方案总数。

样例数据

5

6

样例解释

5 = 1+1+1+1+1
5 = 3+1+1
5 = 1+3+1
5 = 1+1+3
5 = 4+1
5 = 1+4

数据范围

对60%的数据，$\le n \le 50$；

对100%的数据，$5 \le n \le 5000$。