题目背景

似此星辰非昨夜，却道故人心易变。

题目描述

璀璨星空下，白果给 Genius_Star 出了一些数学题。

我们把一个数称为符合条件的，当且仅当它满足以下所有条件：

• 它的数字只包含 $0,1,2,3,4$，且这五个数字都出现过至少一次。

• 所有的 $0$ 都出现在所有的 $1$ 之前，且所有的 $3$ 都出现在所有的 $4$ 之前。

• 最高位数字不为 $0$。

Genius_Star 需要求出恰好有 $n$ 位的符合条件的数的个数。当然，这个数可能很大，而白果不想让他太累，所以答案还需要对 $10^9+7$ 取模。

他不会这个问题，所以交给你了。

输入格式

输入共 $2$ 行。

第一行输入一个正整数 $l$，表示 $n$ 的位数。

第二行输入一个正整数 $n$。

输出格式

输出共 $1$ 行。

一个正整数，表示答案。

1
5

18

1
6

200

提示

样例解释 #1：

符合条件的 $5$ 位数为：

$$20134,20314,20341,23014,23041,23401,30124,30142,30214,\\30241,30412,30421,32014,32041,32401,34012,34021,34201$$

数据范围与约定：

本题采用捆绑测试。

子任务编号	分值	$n \leq$
$1$	$10$	$10^3$
$2$	$20$	$10^7$
$3$	$30$	$2^{10^4}$
$4$	$40$	$10^{10^7}$

对于 $100 \%$ 的数据，保证 $1 \le n \le 10^{10^7}$。