题目描述

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

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

输入格式

一个整数 n。

输出格式

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

数据范围与约定

1≤n≤5000。

可见测试数据

输入数据 1

3

输出数据 1

48

输入数据 2

100000

输出数据 2

382019221

输入数据 3

1

输出数据 3

1