const MOD: usize = 1e9 as usize + 7; fn main() { let mut t = String::new(); std::io::stdin().read_line(&mut t).ok(); let t = t.trim().chars().collect::>(); let mut d = String::new(); std::io::stdin().read_line(&mut d).ok(); let d: usize = d.trim().parse().unwrap(); if d == 0 { if !t.iter().any(|&c| c != '?' || c != '0') { println!("1"); } else { println!("0"); } return; } let total = t.iter().filter(|&&c| c != '?').map(|&c| c as usize - '0' as usize).sum::(); let total = if total == 0 { 0 } else if total % 9 == 0 { 9 } else { total % 9 }; let cnt = t.iter().filter(|&&c| c == '?').count(); let mut dp = vec![vec![0usize; 10]; cnt+1]; dp[0][0] = 1; for i in 0..cnt { for j in 0..=9 { if dp[i][j] == 0 { continue; } for k in 0..=9 { if j == 0 && k == 0 { dp[i+1][0] += dp[i][j]; dp[i+1][0] %= MOD; continue; } let idx = (j+k) % 9; let idx = if idx == 0 { 9 } else { idx }; dp[i+1][idx] += dp[i][j]; dp[i+1][idx] %= MOD; } } } let mut result = 0usize; for i in 0..10 { let idx = if i + total > 0 { if (i+total) % 9 == 0 { 9 } else { (i+total)%9 } } else { 0 }; if idx == d { result += dp[cnt][i]; } } println!("{}", result); }