题目内容

塔子哥是一个热爱编程的少年，他喜欢用 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