题目描述

由数字 1,2,3,4,5 组成的 n 位数，要求 n 位中包含数码 5，且 3 不能出现在 5 前面。求所有这种 n 位数的个数。

答案可能很大，你只需要输出答案除以 $10^{9}+7$ 的余数。

输入格式

一个整数 n。

输出格式

输出答案除以 $10^{9}+7$ 的余数。

3

48

5000

14748326

1

1

数据范围与约定

1≤n≤5000。