暴力计算

//本来想写DP,写着写着成了暴力，= =
//因为和最大为450，直接暴力求出所有可能的和的个数，最后计算和为3的倍数的个数和，即可。。。
#include<bits/stdc++.h>
using namespace std;

#define ffor(i, a, b) for(int i = (a); i<(b); i++)
typedef long long ll;
const int MOD=1e9+7;
const int maxn=460;
ll a[55], d[450], len, sum;

void Read(){
    char c = getchar();
    while(isdigit(c)){
        a[++len] = c-'0' , c=getchar();
        sum+=a[len];
    }
}

int main(){
    Read();

    d[a[1]]++;
    for(int i=2; i<=len; i++){
        for(int j=sum; j>=a[i]; j--){
            if(d[j-a[i]] > 0) d[j]+=d[j-a[i]];
        }
        d[a[i]]++;
    }
    ll ans= 0;
    for(int i=0; i<=sum; i+=3){
        ans = (ans+d[i])%MOD;
    }
    cout <<ans;
    return 0;
}