We say that a string of digits from $0$ to $9$ is valid if the following conditions hold: First, for $2 \le k \le 4$, no consecutive run of $k$ digits sums to a multiple of $10$. Second, between any two $0$s, there are at least $3$ other digits. Find the last four digits of the number of valid strings of length $2020$.

Let's think step by step and output the final answer within \boxed{}.
user