#include <bits/stdc++.h>
using namespace std;

#define sz(x) x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
    string s;
    cin >> s;
    int n0 = 0, n1 = 0, n2 = 0, ne = 0, t, mil = 1000000000;
    for(int i = 0; i < s.size(); ++i){
        t = int(s[i] - '0');
        bool bs = t ? 1 : 0;
        ne += !bs;
        t = t%3;
        if(t == 0){
            n0 = (n0*2 + bs) % mil;
            n1 = (n1*2) % mil;
            n2 = (n2*2) % mil;
        } else if(t == 1){
            int t0 = n0, t1 = n1, t2 = n2;
            n1 = (t1 + t0 + 1) % mil;
            n2 = (t2 + t1) % mil;
            n0 = (t0 + t2) % mil;
        } else {
            int t0 = n0, t1 = n1, t2 = n2;
            n2 = (t2 + t0 + 1) % mil;
            n0 = (t0 + t1) % mil;
            n1 = (t1 + t2) % mil;
        }
    }

    cout << (n0 + ne) % mil;
}