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: Wrong Answer

Solution code:
(N,) = [int(x) for x in input().split()]

MOD = 10 ** 9 + 7

if N <= 1:
    print(1)
    exit()
else:
    total = pow(10, N, MOD)
    noZeroes = pow(9, N, MOD)
    noNines = pow(9, N, MOD)
    noZeroOrNines = pow(8, N, MOD)
    print((total - noZeroes - noNines + noZeroOrNines) % MOD)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
if ans < 0:
    print(ans+mod)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

ten=1
nine=1
eight=1

mod=10**9+7

for i in range(N):
    ten *=10
    ten %=mod
    nine *=9
    nine %=mod
    eight *=8
    eight %=mod
print(ten-2*nine+eight)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 1000000007
A = pow(10, N, MOD)
B = pow(9, N, MOD)
C = pow(8, N, MOD)
X = A - 2 * B + C
print(X)

Submission status: Wrong Answer

Solution code:
N = int(input())

M = 10**9+7
print(pow(10, N, M)-pow(9, N, M)*2+pow(8, N, M))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
A=1000000007
x=10**n - 8**n
print(x%A)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10 ** 9 + 7
res = (10 ** N) % mod
res -= (9 ** N) % mod # no 9
res -= (9 ** N) % mod # no 0
res += (8 ** N) % mod # no 9 and no 0
print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
M = 10**9+7
v1 = pow(9, n, M)
v2 = pow(8, n, M)
ans = pow(10, n, M) - v1*2 + v2
print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())

res = pow(10, N, MOD) - (2 * pow(9, N, MOD) - pow(8, N, MOD))
print(res)

Submission status: Wrong Answer

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

#10 ** N - 2 * (9 ** N) + (8 ** N)
ten = 1
nine = 1
eight = 1
for i in range(N):
  ten *= 10
  ten %= mod
  nine *= 9
  nine %= mod
  eight *= 8
  eight %= mod
  
ans = ten - 2 * nine + eight  
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 10**9 + 7
def f(x, y): return pow(x, y, MOD)
print(f(10, N) - f(9, N) - f(9, N) + f(8, N))

Submission status: Wrong Answer

Solution code:
n=int(input())
mod=int(1e9+7)
if n==1:
  print(0)
else:
	print(2*pow(10,n-2,mod)%mod)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N = I()
    print(pow(10, N, MOD) - (pow(9, N, MOD) + pow(9, N, MOD) - pow(8, N, MOD)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    mod = 10**9+7
    print(pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
if n <= 1:
    print(0)

else:

    mod = 10 ** 9 + 7

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
a = pow(9, n, MOD)
b = pow(8, n, MOD)
c = pow(10, n, MOD)

print(c - 2*a + b)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    x = 10 ** 9 + 7
    
    kosuu = 10 ** n % x  - 9 ** n % x - 9 ** n % x + 8 ** n % x
    print(kosuu)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
print(pow(10,N,1000000007)-2*pow(9,N,1000000007)+pow(8,N,1000000007))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
ans = (10 ** N) % MOD - (9 ** N) * 2 % MOD + (8 ** N) % MOD
print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
md=10**9+7
if n==1:
  print(0)
else:
  an=2*(pow(10,n-2,md))
  print(an%md)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())

ret = pow(10, n, MOD)
ret -= pow(9, n, MOD)
ret -= pow(9, n, MOD)
ret += pow(8, n, MOD)

print(ret)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

MODULUS = 10**9+7

N = int(input())

ret = pow(10, N, MODULUS)
ret -= 2*pow(9, N, MODULUS)
ret += pow(8, N, MODULUS)

print(ret)

Submission status: Wrong Answer

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

'''
Author: andyli
Time: 2020-09-13 19:58:05
'''

import os
from io import BytesIO, IOBase
import sys


MOD = 10**9+7
def main():
    n = int(input())
    print(pow(10,n,MOD)-pow(9,n,MOD)*2+pow(8,n,MOD))
    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
import sys
input = sys.stdin.readline
N = int(input())

ans = pow(10,N,MOD)
ans -= 2*pow(9,N,MOD)
ans += pow(8,N,MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()

ans = pow(10,N,MOD)
ans -= pow(9,N,MOD)
ans -= pow(9,N,MOD)
ans += pow(8,N,MOD)
print(ans)

Submission status: Wrong Answer

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)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def biquity():
    N=input()
    N=int(N)
    i=N
    k=0
    l=0
    while i>0:
        i += -1
        l += 1
        k += 8**(N-l)*comb(N,l)
    answer=10**N-(8**N+2*k)
    answer=answer%(10**9+7)
    
    print(answer)

biquity()

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def biquity():
    N=input()
    N=int(N)
    i=N
    k=0
    l=0
    while i>0:
        i += -1
        l += 1
        k += 8**(N-l)*comb(N,l)
    answer=10**N-(8**N+2*k)
    print(answer)

biquity()

Submission status: Time Limit Exceeded

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

# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=10**9+7
ans=0
temp1=1
temp2=1
temp3=pow(2,n,mod)
for i in range(n-1):
    ans+=(((temp1*temp2)%mod)*(temp3%mod-2))%mod
    temp1=((temp1*(n-i))*pow(i+1,mod-2,mod))%mod
    temp2=(temp2*8)%mod
    temp3=pow(2,n-i-1,mod)
    
 
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = 0
A_zero = str(A).zfill(N)
B = 0

if N == 0 or N == 1:
    print(0)
elif N >= 2:
    while int(A_zero) < 10**(N):
        if '0' in A_zero and '9' in A_zero:
            B += 1
        A += 1
        A_zero = str(A).zfill(N)
    x = B % (10**9 + 7)
    print(x)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def fact(n):
  ans = 1
  for num in range(n):
    ans = (ans*(num+1))%mod
  return ans
def power(a,m,mod):
  if m == 0:
    return 1
  elif m%2 == 0:
    return power(a*a%mod,m//2,mod)%mod
  else:
    return a*power(a,m-1,mod)%mod
  

N = int(input())
if N == 1:
  print(0)
else:
  ans = 0
  for n1 in range(N-1):
    n1 += 1
    for n2 in range(N-n1):
      n2 += 1
      tmp1 = (fact(N)*fact(N-n1)) % mod
      tmp2 = fact(N-n1)
      tmp3 = fact(N-n1-n2)
      tmp4 = power(tmp2,mod-2,mod)*power(tmp3,mod-2,mod)*power(fact(n1),mod-2,mod)*power(fact(n2),mod-2,mod)*power(8,N-n1-n2,mod)
      #print(tmp1,tmp4)
      tmp1 *= power(tmp2,mod-2,mod)*power(tmp3,mod-2,mod)*power(fact(n1),mod-2,mod)*power(fact(n2),mod-2,mod)*power(8,N-n1-n2,mod)
      
      ans = (ans+tmp1)%mod
  print(ans)

Submission status: Time Limit Exceeded

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

N = int(readline())

DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N + 1)]

dp[0][0] = 1

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

Submission status: Time Limit Exceeded

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

N = int(readline())

DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N + 1)]

dp[0][0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N = int(input())
comb = Combination(N + 10)

dis = 0
for i in range(1, N + 1):
    dis += comb.ncr(N, i) * 2 * pow(8, N - i, MOD)
    dis %= MOD
ans = pow(10, N, MOD) - dis - pow(8, N, MOD)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10 ** 9 + 7
ans = 0
factorial = [1]
for i in range(1, n + 2):
    factorial.append(factorial[-1] * i % mod)

factorial_inv = [pow(x, mod - 2, mod) for x in factorial]


def nchooser(n, r):
    return ((factorial[n] * factorial_inv[r] % mod) * factorial_inv[n - r]) % mod


p9 = [1]
p8 = [1]

for i in range(n + 2):
    p9.append(p9[-1] * 9 % mod)
    p8.append(p8[-1] * 8 % mod)

for nines in range(1, n):
    rem = n - nines
    val = (p9[rem] - p8[rem]) % mod
    val *= nchooser(n, nines)
    val %= mod
    if val < 0:
        val += mod
    ans = (ans + val) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10 ** 9 + 7
ans = 0
factorial = [1]
for i in range(1, 10 ** 6 + 10):
    factorial.append(factorial[-1] * i % mod)


def power(x, y, p):
    res = 1  # Initialize result

    # Update x if it is more
    # than or equal to p
    x = x % p

    if (x == 0):
        return 0

    while (y > 0):

        # If y is odd, multiply
        # x with result
        if ((y & 1) == 1):
            res = (res * x) % p

            # y must be even now
        y = y >> 1  # y = y/2
        x = (x * x) % p

    return res


factorial_inv = [power(x, mod - 2, mod) for x in factorial]


def nchooser(n, r):
    return ((factorial[n] * factorial_inv[r] % mod) * factorial_inv[n - r]) % mod


p9 = [1]
p8 = [1]

for i in range(n + 1):
    p9.append(p9[-1] * 9 % mod)
    p8.append(p8[-1] * 8 % mod)

for nines in range(1, n):
    rem = n - nines
    val = (p9[rem] - p8[rem]) % mod
    val *= nchooser(n, nines)
    val %= mod
    if val < 0:
        val += mod
    ans = (ans + val) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**9 + 7
ans = 0
factorial = [1]
for i in range(1, 10**6+10):
    factorial.append(factorial[-1] * i % mod)


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


for nines in range(1, n):
    rem = n - nines
    val = (pow(9, rem, mod) - pow(8, rem, mod)) % mod
    val *= nchooser(n, nines)
    val %= mod
    if val < 0:
        val += mod
    ans = (ans + val) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
con = 1;
a = 1;
b = 1;
 
for i1 in range(n):
    con = (con * 10);
for i2 in range(n):
    a = (a * 9);
for i3 in range(n):
    b = (b * 8);
 
c = 2*a - b;
con = (con - c)%1000000007;
print(con)

Submission status: Time Limit Exceeded

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

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

dp = [[0]*4 for _ in range(n+1)]

dp[2][0] = 64
dp[2][1] = 17
dp[2][2] = 17
dp[2][3] = 2
for i in range(2, n):
    dp[i+1][3] = ((dp[i][1] + dp[i][2]) % mod + dp[i][3]*10 % mod) % mod

    dp[i+1][1] = (dp[i][0] + dp[i][1]*9 % mod) % mod

    dp[i+1][2] = (dp[i][0] + dp[i][2]*9 % mod) % mod

    dp[i+1][0] = (dp[i][0]*8) % mod
print(dp[n][3])

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
if N == 1:
    ans = 0
else:
    # N == 3
    # [[0|9], [0|9], [1-8]] = (3! * 8^1 * (2^2 - 2)) / 2! * 1!
    # [[0|9], [0|9], [0|9]] = (3! * 8^0 * (2^3 - 2)) / 3! * 0!
    # N == 4
    # [[0|9], [0|9], [1-8], [1-8]] = (4! * 8^2 * (2^2 - 2)) / 2! * 2!
    # [[0|9], [0|9], [0|9], [1-8]] = (4! * 8^1 * (2^3 - 2)) / 3! * 1!
    # [[0|9], [0|9], [0|9], [0|9]] = (4! * 8^0 * (2^4 - 2)) / 4! * 0!
    ans = 0
    factorial_N = factorial(N)
    factorial_r = factorial_N // N
    e = 8 ** (N-2)
    t = 2
    rem = N - 2
    for i in range(2, N+1):
        t *= 2
        factorial_N = factorial_N // i
        factorial_r = factorial_r // (rem + 1)
        ans += ((factorial_N * e * (t - 2)) // factorial_r) % (10**9 + 7)
        e = e // 8
        rem -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = 10**6 + 7
MOD = 10**9 + 7
c = [1] * N


def quick(a, b):
    res = 1
    while b:
        if b & 1:
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return (res % MOD)

n = int(input())

for i in range(1, N):
    c[i] = (i * c[i - 1]) % MOD

ans = quick(10, n) - quick(8, n)
cnt = 0

for i in range(1, n + 1):
    x = (c[i] * c[n - i]) % MOD
    y = (c[n] * quick(x, MOD - 2)) % MOD
    z = (y * quick(8, n - i)) % MOD
    cnt = (cnt + z) % MOD

ans = (ans - 2 * cnt) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

cnt = 0
for i in range(pow(10, n)-1):
  if ("0" in str(i).zfill(n)) & ("9" in str(i).zfill(n)):
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

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

#print(ans%mod)

p=[]

for i in range(10**n):
    p.append(str(i).zfill(n))

a=0
for i in p:
    if("0"in i and "9" in i):
        a+=1

#print(len(p))
print(a%mod)
#print(p)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

import numpy as np
from scipy.special import comb

N = int(input())
if N < 2:
    print(0)
    sys.exit()

# Num of arrays consist of 0 and 9 only
# (but subtract a number of 0-only and 9-only arrays)
ans = np.power(2, N) - 2
x = 1
while 2 + x <= N:
    # Fill x sheets by 1~8
    ans += (np.power(2, (N - x)) - 2) * comb(N, x, exact=True) * np.power(8, x)
    x += 1
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
count = 0
list = [[0,1,2,3,4,5,6,7,8,9]]*n
# print(list)
a = [0]*n
for i in range(10**n):
    for j in range(n):
        a[j] = ((i%10**(j+1))//10**j)

    notcount0 = 0
    notcount9 = 0
    for j in range(n):
        # print(str(a[j]),end='')
        if a[j] != 0:
            notcount0 += 1
        if a[j] != 9:
            notcount9 += 1
    if notcount0 != n and notcount9 != n:
        count += 1
    print('')
count = count%(10**9+7)
print(count)

Submission status: Time Limit Exceeded

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

ret = 0
prev = 0
for i in range(1, N+1):
    if prev == 0:
        val = 8**(i-1) * 9**(N-i)
    else:
        val = prev * 8 // 9
    ret = (ret+val) % MOD
    prev = val

print((10**N - 8**N - ret*2)%MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())

# N == 3
# [[0|9], [0|9], [1-8]] = (3! * 8^1 * (2^2 - 2)) / 2! * 1!
# [[0|9], [0|9], [0|9]] = (3! * 8^0 * (2^3 - 2)) / 3! * 0!
# N == 4
# [[0|9], [0|9], [1-8], [1-8]] = (4! * 8^2 * (2^2 - 2)) / 2! * 2!
# [[0|9], [0|9], [0|9], [1-8]] = (4! * 8^1 * (2^3 - 2)) / 3! * 1!
# [[0|9], [0|9], [0|9], [0|9]] = (4! * 8^0 * (2^4 - 2)) / 4! * 0!

ans = 0
factorial_N = factorial(N)
factorial_r = factorial_N // N
e = 8 ** (N-2)
t = 2
rem = N - 2
for i in range(2, N+1):
  t *= 2
  factorial_N = factorial_N // i
  factorial_r = factorial_r // (rem + 1)
  ans += (factorial_N * e * (t - 2)) // factorial_r
  e = e // 8
  rem -= 1

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

Submission status: Time Limit Exceeded

Solution code:
import math

# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

def comb(n,k,p):
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p


def main():
    n = int(input())
    mod = 10**9 + 7
    ans = 0
    # for i in range(n):
    #     ans += 10
    if n==1:
        print(0)
        return
    
    ans += power_func(10, n, mod)
    ans -= power_func(8, n, mod)
    ans %= mod
    
    for i in range(1, n+1):
        a = 2 * comb(n, i, mod)
        b = (a * power_func(8, n-i, mod)) % mod
        ans -= b
        ans %= mod
    
    ans %= mod
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())

den = int(1e9 + 7)
c = lambda a, b: (math.factorial(a) // (math.factorial(a - b) * math.factorial(b)))
ans = 0
if n == 1:
    ans = 0
elif n == 2:
    ans = 2
else:
    for i in range(2, n + 1):   # number of 0|9
        ans = (ans + (8 ** (n - i) * (2 ** i - 2) * c(n, i))) % den
print(ans)

Submission status: Time Limit Exceeded

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

if n == 1:
  print(0)
else:
  a = 2
  aa = 1
  for i in range(2,n):
    aa = (9*aa+10**(i-1))%m
    a = (aa*2+8*a)%m
  print(a%m)