Count numbers deleted by removing consecutive digit pairs that don't sum to 17

Below is the problem statement that I have:

You get number written in base 10, you have to delete it completely by choosing two consecutive digits and deleting them. But the sum of those 2 digits should not be 17. We call the numbers which are fully deleted by repeating the above operation as "Good".

Example:

1. 9889 => Delete 88 to get 99
2. 99 => Delete 99 to fully delete number.
   Conclusion: 9889 is good.
   NOTE: We cannot remove 98 or 89 as the sum of these 2 digits is 17.

Given a number N(even) you want to find the number of good N-digit number modulo 10^9 + 7. Include in the count the N digit numbers containing leading zeros, too.

Test Cases:

Case 1:

Input: 2
Output: 98

Case 2:

Input: 4
Output: 9926

Case 3:

Input: 442
Output: 417551213

I have tried solving this using various codes but not able to get the result.

For each sequence of the last possible bad state, there must have been a forced sequence that generated it. Look at the locations of possible wild-cards (the digits that offer choice are the ones of interest, of course), and try to find a pattern.

In the following examples, for symmetry, switch 9s with 8s; xs are wildcards:

Input length 4, bad result 9898:

9898

Input length 4, bad result 98:

989x
98x8
9x98
x898

We can clearly see from the two above why we get the output, 9926 good 4-digit numbers.

Input length 6, bad result 9898:

98989x
9898x8
989x98
98x898
9x9898
x89898

Input length 6, bad result 9898 OR 98:

9898xx
989xx8
98xx98
9xx898
xx9898

Input length 6, bad result 98:

989x9x
98x8x8
...
9x989x
...

etc.

Python code:

# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
  if not 0<=k<=n: return 0
  b=1
  for t in range(min(k,n-k)):
    b*=n; b//=t+1; n-=1
  return b
def f(n):
  bads = 0
  
  for k in range((n - 2) // 2 + 1):
    bads += 9**k * binom(n, k)
  
  return (10**n - 2 * bads) % (10**9 + 7) 
  
print(f(442)) # 417551213

Try with using a tree to try every possible solution. The real problem is that, you have to predict what digit will stay and if you can delete them without having a sum of 17.
For exemple, if you have 9823 you can delete 23 but you'll be blocked with 98 at the end.

You can try building a tree with every branch being a possibility of deletion. If all of the branches are blocked you get back to the previous node

Not wanting to spoil the coding, but whether a number is good, could be done with backtracking.

    solve(9889);
public static void solve(int num) {
try {
solve(num, new LinkedList<>());
System.out.println("Not found");
} catch (FoundException fe) {
System.out.printf("%d%n", num);
fe.result.forEach(pair -> System.out.printf("-> %d, having deleted %d%n",
pair.getKey(), pair.getValue()));
}
}
private static class FoundException extends RuntimeException {
public final List<Pair<Integer, Integer>> result;
public FoundException(List<Pair<Integer, Integer>> result) {
this.result = result;
}
}
private static void solve(int num, LinkedList<Pair<Integer, Integer>> partialResult) {
if (num == 0) {
throw new FoundException(partialResult);
}
int tenPower = 1;
while (num >= tenPower) {
int n = num / tenPower;
int del = n % 100;
if (del % 10 + del / 10 != 17) {
int n2 = (n / 100) * tenPower + (num % tenPower);
partialResult.addLast(new Pair<>(n2, del));
solve(n2, partialResult);
partialResult.removeLast();
}
tenPower *= 10;
}
}

The problem seems to be formulated such that an int (31 bits unsigned int) suffices.
Hence I tried working with int instead of a list of digits.

An other feature: using an exception to return from deep inside recursion to the top level with a positive result. The traditional way would be to check the result of a recursive call.

Note: the actual problem is a more mathematical one.