Problem K: 危险的组合

上一题 正确率: $81.51\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1060$ 正确数量 $864$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划 递推

Description

有一些装有铀(用U表示)和铅(用L表示)的盒子，数量均足够多。要求把N个盒子放成一行，但至少有3个U放在一起，有多少种方法？

Input

第一行包含一个整数N(3<=N<=30)。

Output

输出一个整数表示方法数(结果模1000000007)。

Sample Input复制

4

Sample Output复制

3

提示

3<=N<=30 

输入：
4 
 

输出：
3
样例解释1：UUUL、LUUU、UUUU