$N^2$解。 f1是计算子区间里面子序列的贡献

题目内容

对于一个由字符 A、B、C 构成的字符串，我们定义它的“魅力值”为该字符串中包含的子序列 ABC 的数量（子序列可以不连续）。

定义一个字符串的“总魅力”为其所有连续子串的魅力值之和。

现在，考虑所有长度为 $n$ 的、仅由字符 A、B、C 组成的字符串（共计 $3^n$ 个）。请你求出这些字符串的总魅力之和，并对 $10^9+7$ 取模。

约束条件：$n$ 为正整数，且 $1 \le n \le 1000$。

输入描述

输入包含一行，一个正整数 $n$ ($1 \le n \le 1000$)。

输出描述

输出一个整数，表示所有长度为 $n$ 的字符串的总魅力之和对 $10^9+7$ 取模后的结果。

样例1

输入

1

输出

0

说明

字符串长度 $n = 1$。所有可能的字符串为 "A"、"B"、"C"，共 $3^1 = 3$ 个。由于长度不足 $3$，任何字符串都无法包含子序列 "ABC"，故每个字符串的魅力值为 $0$，总魅力之和也为 $0$。对 $10^9+7$ 取模后结果为 0。

样例2

输入

3

输出

1

说明

字符串长度 $n = 3$。此时每个字符串的子串只有其自身，长度为 $3$。计算字符串的魅力值即统计其中子序列 "ABC" 的数量。只有当字符串恰好为 "ABC" 时，魅力值为 1；其余 $26$ 个字符串的魅力值均为 $0$。全部 $3^3 = 27$ 个字符串的总魅力之和为 $1$。取模后仍为 1。

样例3

输入

4

输出

18

说明

字符串长度 $n = 4$。总魅力之和由所有连续子串贡献，子串长度可为 $3$ 或 $4$。设 $g(k)$ 为所有长度为 $k$ 的字符串魅力值之和，有 $g(k) = \binom{k}{3} \cdot 3^{k-3}$。对于长度 $3$ 子串：每个长度为 $4$ 的字符串有 $2$ 个长度 $3$ 子串，剩余 $1$ 个位置可任意选 $3$ 种字符，贡献为 $g(3) \times 3^{1} \times 2 = 1 \times 3 \times 2 = 6$。对于长度 $4$ 子串：每个字符串恰好有 $1$ 个自身，无剩余位置，$g(4) = \binom{4}{3} \cdot 3^{1} = 12$，贡献为 $12 \times 3^{0} \times 1 = 12$。合计 $6 + 12 = 18$，取模后为 18。