题目描述

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

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

输入格式

一个整数 n。

输出格式

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

数据范围与约定

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

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

可见测试数据

输入数据 1

3

输出数据 1

6

输入数据 2

2

输出数据 2

0

输入数据 3

199997

输出数据 3

837597358