被3整除的子序列

#include<cstring>

using namespace std;
typedef long long ll;
const int mod = 1e9+7;

int (){
	string ss;
	cin>>ss;
	int len = ss.length();
	int dp[55][3];
	memset(dp,0,sizeof(dp));
	dp[0][(ss[0]-'0')%3]=1;
	for(int i=1;i<len;i++){
		int m=(ss[i]-'0')%3;

		for(int j=0;j<3;j++){
			dp[i][j]=(dp[i-1][j]+dp[i-1][(j+3-m)%3])%mod;//dp公式
		}
		dp[i][m]=(dp[i][m]+1)%mod;//初始化时为0，故计算时需加1
	}
	cout<<dp[len-1][0]%mod<<endl;
	
	return 0;
}