DIVFOUR - Editorial

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI (atan(1)*4)
#define mp make_pair
using namespace std;

//modulo op

ll mod = 1e9 + 7;

ll add(ll a, ll b) {
    return (a + b) % mod;
}

ll sub(ll a, ll b) {
    return ((a - b) % mod + mod) % mod;
}

ll mul(ll a, ll b) {
    return (a * b) % mod;
}
//end of modulo op

ll dp[10], ans, pow2 = 1;
string s;
int main()
{
    fastread;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        int lastdig = s[i] - '0';
        if (lastdig % 4 == 0)
            ans = add(ans, 1);
        for (int j = 0; j < 10; j++) {
            int last2dig = j * 10 + lastdig;
            if (last2dig % 4 == 0)
                ans = add(ans, dp[j]);
        }
        dp[lastdig] = add(dp[lastdig], pow2);
        pow2 = mul(2, pow2);
    }
    cout << ans;
    return 0;
}