You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

塔子哥是一个热爱编程的少年，他喜欢用 red 字符串来编写自己的程序。他认为 red 字符串是最美丽的字符串，因为它代表了热情、活力和创造力。他经常用 red 字符串来做各种有趣的实验，比如生成随机图案、加密解密信息、模拟物理现象等等。

有一天，塔子哥在网上看到了一个编程竞赛，要求参赛者用 red 字符串来完成一个复杂的任务。塔子哥很感兴趣，决定挑战自己。他下载了题目，发现是一个关于字符串权值的数学问题。塔子哥觉得这个问题很有意思，因为它可以测试他对 red 字符串的理解和掌握。

题目里给定了一个字符串的美丽度为：该字符串包含的 red 子序列的数量。（注意：子序列是可以不连续的），然后又给定了一个字符串的权值为：该字符串所有连续子串的美丽度之和。然后题目的问题是：长度为 $n$ 的、仅由字符 r 、 e 、 d 构成的所有字符串(共有 $3^n$ 个字符串)的权值之和是多少？（答案请对 $10^9+ 7$ 取模。）

现在塔子哥想知道这个题目怎么写，你能帮帮他吗？

输入描述

第一行输入一个正整数 $n$ 。（ $1\le n \le 1000$ ）

输出描述

输出一个整数，表示长度为 $n$ 的、仅由字符 r 、e、 d构成的所有字符串的权值之和。

样例

输入

4

输出

18

提示

对于字符串$rred$ , 它的子串是 $\{r,rr,rre,rred,r,re,red,e,ed,d\}$，其中$rred$ 的美丽值是 2 , $red$ 美丽值是1。所以权值是2 + 1 = 3