Problem:


Score : 300 points

Problem Statement

How many integer sequences A_1,A_2,\ldots,A_N of length N satisfy all of the following conditions?

0 \leq A_i \leq 9

There exists some i such that A_i=0 holds.

There exists some i such that A_i=9 holds.

The answer can be very large, so output it modulo 10^9 + 7.

Constraints

1 \leq N \leq 10^6

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer modulo 10^9 + 7.

Sample Input 1

2

Sample Output 1

2

Two sequences \{0,9\} and \{9,0\} satisfy all conditions.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

869121

Sample Output 3

2511445



Sample input:
2


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())

MOD = int(1e9) + 7

dp = [[0] * 4 for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
    # 0も9もない
    dp[i][0] = dp[i - 1][0] * 8 % MOD
    # 0だけある
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 9) % MOD
    # 9だけある
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][2] * 9) % MOD
    # 0も9もある
    dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 10) % MOD

print(dp[N][3])

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10**9+7
print((pow(10, n, MOD) - pow(9, n, MOD) * 2 + pow(8, n, MOD)) % MOD)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7

ans = pow(10, n, mod) - 2 * pow(9, n, mod) + pow(8, n, mod)
print(ans % mod)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    m = 10**9+7
    if n == 1:
        print(0)
    elif n == 2:
        print(2)
    else:
        print((10**n - 2*9**n + 8**n)%m)


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
ans=(10**n-9**n-9**n+8**n)%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=(10**n-2*(9**n)+8**n)%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()
ans = 10**n - 2*9**n + 8**n
print(ans%(10**9 + 7))

Submission status: Accepted

Solution code:
n = int(input())
a = 1
b = 1
c = 1
for _ in range(n):
    a *= 10
    a %= 1000000007
    b *= 9
    b %= 1000000007
    c *= 8
    c %= 1000000007
print((a - 2*b + c)%1000000007)

Submission status: Accepted

Solution code:
n = int(input())
lst = [8, 1, 1, 0]
for i in range(n - 1):
    a = lst[0]*8
    b = lst[0] + lst[1]*9
    c = lst[0] + lst[2]*9
    d = lst[3]*10 + lst[1] + lst[2]
    a = a%(10**9 + 7)
    b = b%(10**9 + 7)
    c = c%(10**9 + 7)
    d = d%(10**9 + 7)
    lst = [a, b, c, d]
print(lst[3])

Submission status: Accepted

Solution code:
n = int(input())
k = 10 ** n - 9 ** n * 2 + 8 ** n
print(k % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
ans=pow(10,n,mod)
ans-=pow(9,n,mod)*2
ans+=pow(8,n,mod)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
a = 10**n-8**n
a%=mod
b = 10**n-9**n
b%=mod
c = b*2
d = c-a
d%=mod
print(d)

Submission status: Accepted

Solution code:
def modexp(a,b,mod):
    if b==0:
        return 1
    elif b%2==0:
        x=modexp(a%mod,b//2,mod)%mod
        return (x*x)%mod
    else:
        return ((a%mod)*(modexp(a%mod,b-1,mod)%mod))

mod=10**9+7
n=int(input())
a=modexp(10,n,mod)
b=modexp(9,n,mod)
c=modexp(8,n,mod)
ans=((a+c)%mod)-((2*b)%mod)
print(ans%mod)

Submission status: Accepted

Solution code:
p=10**9+7

ans=0
n=int(input())
kyu=pow(9,n,p)
hati=pow(8,n,p)
ju=pow(10,n,p)

print((p*5+ju-kyu*2+hati)%p)

Submission status: Accepted

Solution code:
N=int(input())
X=10**N-2*9**N+8**N
print(X%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7


def table():
    k = 10 ** 6 + 5  # 変える
    fac = [1] * k
    finv = [1] * k
    inv = [0] * k
    inv[1] = 1
    for i in range(2, k):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


fac, finv = table()


def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


ans = 0
for i in range(2, n + 1):
    ans += comb(n, i) * (pow(2, i, mod) - 2) * pow(8, n - i, mod) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
m = 10**9 + 7
def pos(x, n, m):
    if n == 0:
        return 1
    res = pos(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res
s = pos(10, N, m)
t = pos(9, N, m)
u = pos(8, N, m)
ans = s + u - t - t
ans = ans % m
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

print((10**n-2*(9**n)+8**n)%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())

ans=pow(10,n)+pow(8,n)-2*pow(9,n)
waru=pow(10,9)+7
answer=ans%waru
print(answer)

Submission status: Accepted

Solution code:
## for use in beginner level questions where speed is key
## and also for single test case code
## mastercopy for x,y,z

import sys
import heapq, functools, collections
import random
from collections import Counter, defaultdict

# read line as a string
# strr = input()

# read line as an integer
k = int(input())

# read one line and parse each word as a string
# lst = input().split()

# read one line and parse each word as an integer
# arr = list(map(int,input().split()))

if k == 1:
    print(0)
    sys.exit()

# if k == 2:
#     print(2)
#     sys.exit()

res = 0
MOD = 10**9 + 7

have_all = pow(10,k,MOD)
dont_have_0 = pow(9,k,MOD)
dont_have_9 = pow(9,k,MOD)
dont_have_09 = pow(8,k,MOD)

print((have_all - dont_have_0 - dont_have_9 + dont_have_09) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

mod=10**9+7
n=int(input())
ans=pow(10,n,mod)
ans-=2*pow(9,n,mod)
ans+=pow(8,n,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
if N == 1:
    print(0)
    exit()
ans = 1
dp = [[8, 1, 1, 0] for _ in range(N)]
for i in range(1, N):
    dp[i][0] = dp[i-1][0]*8 % MOD
    dp[i][1] = dp[i-1][1]*9 % MOD+dp[i-1][0]
    dp[i][2] = dp[i-1][1]*9 % MOD+dp[i-1][0]
    dp[i][3] = dp[i-1][3]*10 % MOD+dp[i-1][1]+dp[i-1][1]
print(dp[-1][-1] % MOD)

Submission status: Accepted

Solution code:
N = int(input())

if N == 1:
    print(0)
    exit()

initial = 10
oneornine = 9
oneandnine = 8

for i in range (0, N-1):
    initial*=10
    initial = initial%(10**9+7)

for i in range (0, N-1):
    oneornine*=9
    oneornine = oneornine%(10**9+7)

for i in range (0, N-1):
    oneandnine*=8
    oneandnine = oneandnine%(10**9+7)

print((initial-2*oneornine+oneandnine)%(10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

n = int(input())

mod = 10**9+7

res = pow(10,n,mod) - 2*pow(9,n,mod) + pow(8,n,mod)

print(res%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 1000000007
ans = 10**n - 2*(9**n) + 8**n
print(ans % mod)

Submission status: Accepted

Solution code:
n=int(input())
ten=1
nine=1
eight=1
mod=1000000007
for i in range(n):
    ten=(ten*10)%mod
    nine=(nine*9)%mod
    eight=(eight*8)%mod
print((ten-nine*2+eight)%mod)

Submission status: Accepted

Solution code:
N = int(input())

ans = 10**N - 2*(9**N) + 8**N

k = 10**9 + 7

print(ans % k)

Submission status: Accepted

Solution code:
def mpower(a, b, n):
    if b==0:
        return 1
    if b==1:
        return a%n
    a1=a
    k=1
    while a1<n and k<b:
        a1=a1*a
        k=k+1

    a1=a1%n
    b1=b//k
    a2=a
    b2=b%k
    return (mpower(a1,b1,n)*mpower(a2,b2,n))%n

m = 10**9+7
n = int(input())

print((mpower(10,n,m) + (m - mpower(9,n,m))*2 + mpower(8,n,m))%m)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
a = pow(10,N,mod)
b = pow(8,N,mod)
c = pow(9,N,mod)
ans = a-2*c+b
while ans<0:
    ans += mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ans = 10**N-((9**N)*2-8**N)

print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
def pow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res *= x
        x *= x
        n >>= 1
    return res
print((pow(10, n)%mod -2*pow(9, n)%mod + pow(8, n)%mod)%mod)

Submission status: Accepted

Solution code:
N = int(input())
ans = ((10**N)-((9**N)*2)+(8**N))%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
print(((10**N-9**N)*2-10**N+8**N)%(10**9+7))

Submission status: Accepted

Solution code:
import sys
N = int(input())
mod = 10**9 + 7
if N == 1:
  print(0)
  sys.exit()
if N >= 2:
  ans0 = [0]*(N+1)
  ans  = [0]*(N+1)
  ansp = [0]*(N+1)
  ans0[1] = 1
  ansp[1] = 8
  ans[1] = 0
  for i in range(N - 1):
    j = i + 1
    ans[j+1] = (2*ans0[j] + 10*ans[j])%mod
    ans0[j+1] = (9*ans0[j] + ansp[j])%mod
    ansp[j+1] = (ansp[j]*8)%mod
  print(ans[N]%mod)

Submission status: Accepted

Solution code:
n=int(input())

#0-9
#1-9のみ
a8=1
a9=1
a10=1
for i in range(n):
    a8=(a8*8)%(10**9+7)
    a9=(a9*9)%(10**9+7)
    a10=(a10*10)%(10**9+7)
#0-8のみ
print((a10-(2*a9-a8))%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
seq = 10 ** N
seq_eliminate1 = 9 ** N
seq_eliminate2 = 8 ** N
answer = (seq - seq_eliminate1 * 2 + seq_eliminate2) % (10 ** 9 + 7)
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9 + 7
ans = pow(10,N,mod)+pow(8,N,mod)-2*pow(9,N,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
mod = 1000000007
ans = (10**n - 9**n - 9**n + 8**n) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7

ans = pow(10, n, mod)-pow(9, n, mod)*2+pow(8, n, mod)
print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 1000000007 
N = int(input())
print((pow(10, N, MOD) -  2 * pow(9, N, MOD) +  pow(8, N, MOD)) % MOD)

Submission status: Accepted

Solution code:
N = int(input())
MOD_BY = 10**9 + 7

#全通り 10**(N)
#0を1個も含まない　9**(N)
#9を1個も含まない　9**(N)
#0も9を1個も含まない　8**(N)

#https://wakabame.hatenablog.com/entry/2017/09/21/012844
#a**n mod pの高速計算
def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res
  
a = power_func(10,N,MOD_BY)
b = power_func(9,N,MOD_BY)
c = power_func(8,N,MOD_BY)
ans = a - 2*b + c
print(ans%MOD_BY)

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9 + 7

a = N + 100
fact = [0] * (a)
fact[0] = 1
for i in range(1, a):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [0] * a
inv_fact[a-1] = pow(fact[a-1], MOD-2, MOD)
for i in range(a-1, 0, -1):
    inv_fact[i-1] = inv_fact[i] * i % MOD

def nCk(n, k):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % MOD

ans = 0
for i in range(2, N+1):
    ans += nCk(N, i) * (pow(2, i, MOD)-2) * pow(8, N-i, MOD) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


# クラス
class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N = in_n()

    if N == 1:
        print(0)
        exit()

    mod = 10**9 + 7
    comb = CombMod(N + 1)
    ans = 0

    for x in range(2, N + 1):
        t = comb.comb(N, x)
        t *= pow(2, x, mod) - 2
        t %= mod
        t *= pow(8, N - x, mod)
        t %= mod
        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7
a = 1
for i in range(n):
    a *= 10
    a %= mod
b = 1
for i in range(n):
    b *= 9
    b %= mod
b *= 2
b %= mod
c = 1
for i in range(n):
    c *= 8
    c %= mod
print((a - b + c) % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7

N = int(input())

#0がまだどっちもでてない 1が0だけでてる　2が9だけ出てる　3が両方出た
dp = [[0 for i in range(4)]for j in range(N)]
dp[0] = [8,1,1,0]

for i in range(1,N):
    dp[i][0]=(dp[i-1][0]*8)%MOD
    dp[i][1]=((dp[i-1][1]*9)%MOD + dp[i-1][0])%MOD
    dp[i][2]=((dp[i-1][2]*9)%MOD + dp[i-1][0])%MOD
    dp[i][3]=(dp[i-1][1]+dp[i-1][2]+dp[i-1][3]*10)%MOD

print(dp[N-1][3])

Submission status: Accepted

Solution code:
#from collections import deque
#from math import gcd
MOD = 10**9 + 7
N = int(input())
#N, K = map(int, input().split())
#A = list(map(int, input().split()))
ans = 0
#print(ans)
if N == 1:
  print(0)
  exit()
eight = [1]
two = [1]
for k in range(N):
  eight.append(eight[-1]*8%MOD)
  two.append(two[-1]*2%MOD)



fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % MOD)
  inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
  factinv.append((factinv[-1] * inv[-1]) % MOD)

for k in range(2, N+1):
  ans += eight[N-k]*(two[k]-2)%MOD*fact[N]%MOD*factinv[N-k]%MOD*factinv[k]%MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

N = cin()[0]
INF = 10 ** 9 + 7
ans = pow(10, N, INF)
tmp = pow(9, N, INF)
ans -= tmp
ans %= INF
ans -= tmp
ans %= INF
ans += pow(8, N, INF)
ans %= INF
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline())

print(((10**N)-2*(9**N)+(8**N))%(10**9 + 7))

Submission status: Accepted

Solution code:
n=int(input())
kotae=(10**n-2*(9**n)+(8**n))%(10**9+7)
print(kotae)

Submission status: Accepted

Solution code:
N = int(input())

ans = (10 ** N - 2 * (9 ** N) + 8 ** N) % (10 ** 9 + 7)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

kyuN = 9**N
hachN= 8**N
jyuN=10**N


S = jyuN - (kyuN*2-hachN)
print(S%(1000000000+7))

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7

factorials = [1]
for i in range(1, n + 1):
    factorials.append((factorials[-1]) * i % mod)

print((pow(10, n, mod) - pow(9, n, mod) - pow(9, n, mod) + pow(8, n, mod)) % mod)

Submission status: Accepted

Solution code:
N = int(input())
M = 10 ** 9 + 7
def mod_pow(a, b, mod):
	bin_b = []
	while b:
		bin_b.append(b % 2)
		b >>= 1
	ret = 1
	for j in reversed(bin_b):
		ret = (ret * ret) % mod
		if j == 1:
			ret = (ret * a) % mod
	return ret
ans = (mod_pow(10, N, M) - 2 * mod_pow(9, N, M) + mod_pow(8, N, M)) % M
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = pow(10, 9) + 7
ans1 = 1
ans2 = 1
ans3 = 1
for i in range(n):
    ans1*=10
    ans1%=mod
    ans2*=9
    ans2%=mod
    ans3*=8
    ans3%=mod
ans4 = ans2*2
ans4%=mod
ans4 = (ans4+mod)-ans3
ans4%=mod
ans = (ans1-ans4+mod)%mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9 + 7
u = 1
a = 1
b = 1
for i in range(N):
    u = u * 10
    a = a * 9
    b = b * 8
    u = u%mod
    a = a%mod
    b = b%mod
print((u-2*a+b)%mod)

Submission status: Accepted

Solution code:
n = int(input())
MOD = int(1e9 + 7)

dp = [1, 0, 0, 0]
for _ in range(n):
    dp[3] = (dp[1] + dp[2] + 10 * dp[3]) % MOD
    dp[2] = (dp[0] + 9 * dp[2]) % MOD
    dp[1] = (dp[0] + 9 * dp[1]) % MOD
    dp[0] = (8 * dp[0]) % MOD
print(dp[3])

Submission status: Accepted

Solution code:
N = int(input())
ans = ((10 ** N) - (9 ** N) * 2 + (8 ** N)) % (10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=10**n+8**n-2*(9**n)
print(a%(10**9+7))

Submission status: Accepted

Solution code:
int_n = int(input())

ans = 10**int_n -2*(9**int_n) +8**int_n

ans_divide = ans % (10**9 + 7)

print(ans_divide)

Submission status: Accepted

Solution code:
max_int = 10 ** 6
MOD = 10 ** 9 + 7

factorial = [1] * (max_int + 1)
for i in range(2, max_int + 1):
    factorial[i] = (factorial[i - 1] * i) % MOD

def nCr(n, r):
    return (factorial[n] * pow(factorial[n - r], MOD - 2, MOD) * pow(factorial[r], MOD - 2, MOD)) % MOD

N = int(input())
MOD = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N)]
dp[0][0] = 8
dp[0][1] = 1
dp[0][2] = 1
for i in range(1, N):
    dp[i][0] = (dp[i - 1][0] * 8) % MOD
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 9) % MOD
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][2] * 9) % MOD
    dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 10) % MOD
print(dp[-1][3])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate


def read():
    N = int(input().strip())
    return N,


def solve(N, MOD=10**9+7):
    return (pow(10, N, MOD) - pow(9, N, MOD) - pow(9, N, MOD) + pow(8, N, MOD)) % MOD


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
N=int(input())
x=10**9+7
a=pow(10,N,x)
b=pow(9,N,x)
c=pow(8,N,x)
print((a-2*b+c)%x)

Submission status: Accepted

Solution code:
N = int(input())
ans = 10 ** N - 2 * (9 ** N) + 8 ** N
print(ans % (10 ** 9 + 7))