### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Let **S[a…b]** denote the substring from **a**-th character to **b**-th character of **S**.

One of the solutions for this problem is to use the fact that 1000 is multiple of 8. Let consider the number of the integers **S[i**…digit] mod 8 = 0 for all i. This number can be calculated as following:

- count := 0.
- If
**S**[digit] mod 8 = 0 and**S**[digit] ≠ 0, count := count + 1. - If
**S**[digit-1…digit] mod 8 = 0 and**S**[digit-1] ≠ 0, count := count + 1. - If
**S**[digit-2…digit] mod 8 = 0, count := count + the number of non-zero digits in**S**[1…digit-2].

Therefore, at first, calculate the number of non-zero digits in **S**[1…**i**], for all i, then this problem can be solved with **O**(|**S**|) time.

This problem also can be solved by using DP (Dynamic Programming). Let dp[digit][num] = the number of the integers **S[i**…digit] mod 8 = num for all **i**. Then dp[digit+1][aft] = (sum of dp[digit][bef]) + **a**, where (10 * aft + **S**[digit+1]) mod 8 = bef, and if aft = S[digit+1] ≠ 0, **a** = 1, otherwise **a**=0. Note that this algorithm will work for finding the number of the numbers multiple of 7, for example.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.