Problem p02554 (python)

Fixed submission:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

# setrecursionlimit(10**7)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())

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

	for i in range(n):
		for j in range(2):
			for k in range(2):
				for d in range(10):
					nj = j or d == 0
					nk = k or d == 9
					dp[i+1][nj][nk] += dp[i][j][k]
					dp[i+1][nj][nk] %= MOD 

	ans = dp[n][1][1]
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Buggy submission (verdict: Runtime Error):
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define umap unordered_map
#define uset unordered_set
#define pq priority_queue

const ll MOD = 1e9 + 7;

ll pow_mod(ll base, ll exp, ll q) {
	base %= q;
	ll ans = 1;
	while (exp) {
		if (exp & 1) ans = (ans * base) % q;	
		base = (base * base) % q;
		exp /= 2;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n; cin >> n;
	cout << pow_mod(10, n, MOD) - 2*pow_mod(9, n, MOD) + pow_mod(8, n, MOD);
}

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**7)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())

	@lru_cache(None)
	def dp(i, has0, has9):
		if i == n: return 1 if (has0 and has9) else 0
		cnt = 0
		for d in range(10):
			cnt += dp(i+1, has0 or d == 0, has9 or d == 9)
			cnt %= MOD 
		return cnt 

	print(dp(0, 0, 0))

	stdout.close()

if __name__ == "__main__":
	main()

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**5)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())

	@lru_cache(None)
	def dp(i, has0, has9):
		if i == n: return 1 if (has0 and has9) else 0
		cnt = 0
		for d in range(10):
			cnt += dp(i+1, has0 or d == 0, has9 or d == 9)
			cnt %= MOD 
		return cnt 

	print(dp(0, 0, 0))

	stdout.close()

if __name__ == "__main__":
	main()