题目背景

​ “道生一，一生二，二生三，三生万物。”的寓意是表示“道”生万物从少到多，从简单到复杂的一个过程。对于编程的学习来说，也是一个由少到多，由简到繁，由简单到精彩的一个过程。

题目描述

​ 在初始的时候，有一个数字$n$，它会按照以下规则进行$n$次衍变： ​ （假设每次衍变之前，数字中'0'的个数为$a$，数字中'1'的个数为$b$，数字中'2'的个数为$c$）

​ 1.在数字的末位放上一个$a$个数字'1'

​ 2.让整个数字乘上$b$次2

​ 3.在数字的开始位置（左边）放上$c$个'3'

​ 4.如果衍变之前的数字里有'3'，就让数字加上一次123456（无论出现几次'3'，只加一次123456）

​ 5.现在是第几次衍变（从1开始），就加上几

​ 6.将这个数字对$10^9+7$取模

​ 每一次的衍变都要经过过上述的所有规则。

​ 小$t$想知道，这个数字衍变到最后会变成什么。

输入格式

在一行中输入一个整数 $n$。

输出格式

在一行中输出一个整数，表示最终的答案。

输入样例

6

输出样例

3253584

样例解释

初始值 6

第1次衍变： 数字6中没有0-3的数字，所以可以跳过前4步。 然后进行第5步，因为现在是第1次衍变，所以将数字加上1，变成6。 最后进行第6步，对$10^9+7$取模，结果是7。

第2次衍变： 数字7中没有0-3的数字，所以可以跳过前4步。 然后进行第5步，因为现在是第2次衍变，所以将数字加上2，变成9。 最后进行第6步，对$10^9+7$取模，结果是9。

第3次衍变： 数字9中没有0-3的数字，所以可以跳过前4步。 然后进行第5步，因为现在是第3次衍变，所以将数字加上3，变成12。 最后进行第6步，对$10^9+7$取模，结果是12。

第4次衍变： 在衍变开始之前，先统计a，b，c的值（分别代表0、1、2的数量）。在数字12中，有1个'1'，1个'2'，所以刚开始的时候我们得到b=1,c=1。 因为我们的a为0，所以跳过第一步。 进行第2步，需要将数字12乘上b次2，b为1，那么就是乘1次2，12 * 2 = 24。 然后进行第3步，在我们刚刚得到的数字24的左边，放上一个数字'3'，就变成了324。（注意不是24+3=27） 之后进行第4步，首先我们判断一下，衍变之前的数字里有没有'3'。衍变前的数字是12（并不是看第3步之后变成的324中是否有'3'），里面没有'3'，所以跳过这一步。 随后进行第5步，因为现在是第4次衍变，所以将数字324加上4，变成328。 最后进行第6步，对$10^9+7$取模，结果是328。

第5次衍变： 在衍变开始之前，先统计a，b，c的值（分别代表0、1、2的数量）。在数字328中，有1个'2'，所以刚开始的时候我们得到c=1。 数字328中没有'0'、'1'的数字，所以可以跳过前2步。 第3步，在我们刚刚得到的数字24的左边，放上一个数字'3'，就变成了3328。（注意不是328+3=331） 之后进行第4步，首先我们判断一下，衍变之前的数字里有没有'3'。衍变前的数字是328，存在'3'，所以我们将3328加上123456，得到126784。 然后进行第5步，因为现在是第5次衍变，所以将数字126784加上5，变成126789。 最后进行第6步，对$10^9+7$取模，结果是126789。

第6次衍变： 在衍变开始之前，先统计a，b，c的值（分别代表0、1、2的数量）。在数字126789中，有1个'1'，有1个'2'，所以刚开始的时候我们得到b=1,c=1。 因为我们的a为0（衍变前的数字里没有'0'），所以跳过第一步。 进行第2步，需要将数字126789乘上b次2，b为1，那么就是乘1次2，126789 * 2 = 253578。 然后进行第3步，在我们刚刚得到的数字253578的左边，放上一个数字'3'，就变成了3253578。 之后进行第4步，首先我们判断一下，衍变之前的数字里有没有'3'。衍变前的数字是126789，里面没有'3'，所以跳过这一步。 然后进行第5步，因为现在是第6次衍变，所以将数字3253578加上6，变成3253584。 最后进行第6步，对$10^9+7$取模，结果是3253584。

最终的结果就是3253584。

数据范围

对于 $20\%$ 的数据，有 $1\le n \le 8$

对于 $70\%$ 的数据，有 $1\le n \le 10^5$

对于 $100\%$ 的数据，有 $1\le n \le 10^6$