Problem p03178 (python)

Fixed submission:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	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<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 rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

const ll MOD = 1e9 + 7;

void madd(ll& a, ll b){
	a += b;
	if (a >= MOD) a -= MOD;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	string K; cin >> K;
	int D; cin >> D;
	vi lim = vi();
	for(const auto& c : K){
		lim.pb((int)(c - '0'));
	}
	int n = isize(lim);
	ll dp[n+1][2][D];
	rep(i,n+1)rep(j, 2)rep(k, D) dp[i][j][k] = 0;
	dp[0][1][0] = 1;

	for(int i = 0; i < n; i++){
		for(int tight = 0; tight <= 1; tight++){
			for(int ds = 0; ds < D; ds++){
				int md = tight ? lim[i] : 9;
				for(int d = 0; d <= md; d++){
					int nt = (tight and lim[i] == d) ? 1 : 0;
					int nds = (d + ds) % D;
					madd(dp[i+1][nt][nds], dp[i][tight][ds]);
				}
			}
		}
	}
	ll ans = 0;
	madd(ans, dp[n][0][0]);
	madd(ans, dp[n][1][0]);
	cout << ans-1;	
}

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

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(10001)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	@lru_cache(None)
	def dfs(tight, i, tot):
		if i == len(x):
			return 1 if tot == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(ntight, i + 1, (tot + dig) % d)
		return cnt % MOD

	ans += dfs(1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot % d == 0 else 0
		start = 0 if i > 0 else 1
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(start, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, tot + dig)
		return cnt % MOD

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0)
	for i in range(1, len(tupk)):
		bndry = 10**i-1
		ans += dfs(totup(bndry), 1, 0, 0)
		ans %= MOD

	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()