题目描述

由数字 1，2 和 3 组成的 n 位数，要求 n 位数中 1，2 和 3 的每一个至少出现一次。求所有这种 n 位数的个数。

答案可能很大，你只需要输出答案除以 $10^{9}+7$ 的余数。

输入格式

一个整数 n。

输出格式

输出答案除以 $10^{9}+7$ 的余数。

3

6

2

0

199997

837597358

数据范围与约定

80% 数据：1≤n≤$10^{6}$。

100% 数据：1≤n≤$10^{9}$。