package main import ( "fmt" "math" ) func main() { var n int _, _ = fmt.Scan(&n) mod := int(math.Pow10(9)) + 7 fmt.Println(((4*PowMod793(10, n, mod) - 1) * PowMod793(3, mod-2, mod)) % mod) // 1 -> 13 は +12 // 13 -> 133 は +120 // 133 -> 1333 は +1200 // 上記のように、各項は初項12、公比10の等比数列の和となっている // 等比数列の和の公式は(a * r^n - a)/rとなっており、これに当てはめると(12 * 10^n - 12)/9となる // 計算量の多そうな10^nは二分累乗法を使うことでかなり少ない計算回数で実現できる // ただし余りを求めたものの外に割り算があって誤差が出る // これを掛け算にするために、フェルマーの小定理を使う // 1+(12 * 10^n - 12)/9 は (4 * 10^n - 1)/3に変えられる。 // 3も10^9+7もともに素数なので、a^(p-1)≡1(mod p)が成り立つ // 3^(10^9+6)≡1 -> 3^(10^9+5)≡3^-1 // これで1/3は3^(10^9+5)と表現できる // 以上より、(4 * 10^n - 1) * 3^(10^9+5) で答えが出せる } func PowMod793(x, n, mod int) int { if n <= 1 { return x } else if n%2 == 1 { return (PowMod793(x, n-1, mod) * x) % mod } else { m := PowMod793(x, n/2, mod) return (m * m) % mod } }