Problem A: 危险的组合

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1267$ 正确数量 $868$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划 递推
有一些装有铀(用U表示)和铅(用L表示)的盒子,数量均足够多。要求把N个盒子放成一行,但至少有3个U放在一起,有多少种方法?
第一行包含一个整数N(3<=N<=30)。
输出一个整数表示方法数(结果模1000000007)。
4
3

3<=N<=30

输入:
4 
 
输出:
3
样例解释1:UUUL、LUUU、UUUU