/*
状态转移方程：
f[i][j] 表示前i个数中余数为k的个数
f[i][k] = (f[i - 1][k] + f[i - 1][(k - a[i] % 3 + 3) % 3] + f[i][k])
其中f[i - 1][k]表示不算上第i个数为子序列；f[i - 1][(k - a[i] % 3 + 3) % 3]表示算上第i个数为子序列；f[i][k]表示第i个数本身有的个数，不是转移过来的
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55, mod = 1e9 + 7;
int f[N][3];//f[i][j]表示前i个数中余数为k的个数 
int a[N];//转换成数字 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	string s;
	cin >> s;
	int sz = s.size();
	for(int i = 0; i < sz; i++)
		a[i + 1] = s[i] -'0';
	for(int i = 1; i <= sz; i++)
	{
		f[i][a[i] % 3] = 1;
		for(int k = 0; k < 3; k++)
		{
			f[i][k] = (f[i - 1][k] + f[i - 1][(k - a[i] % 3 + 3) % 3] + f[i][k]) % mod;
		}
	}
	cout << f[sz][0] % mod;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1), pre(n + 1), last(n + 2);
	for(int i = 1; i <= n; i++) cin >> a[i];
	pre[0] = last[n + 1] = 0;
	for(int i = 1; i <= n; i++) a[i] > a[i - 1] ? pre[i] = pre[i - 1] + 1 : pre[i] = 1;
    for(int i = n; i >= 1; i--) a[i] < a[i + 1] ? last[i] = last[i + 1] + 1 : last[i] = 1;
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ans = max(ans, max(last[i], pre[i]));
		if(a[i + 1] - a[i - 1] >= 2) ans = max(ans, pre[i - 1] + last[i + 1] + 1);	
	} 
	cout << ans;
	return 0;
}

/*
dp[i][j]的第二维表示以1或0结尾的字符串
因为不能有连续的0，所以dp[i][0]只能由dp[i - 1][1]转移
*/
#include <bits/stdc++.h>
using namespace std;
int dp[25][2];//二维表示分别以1或0结尾 
int main()
{
	int n;
	cin >> n;
	dp[1][1] = dp[1][0] = 1;//初始化
	for(int i = 2; i <= n; i++)
	{
		dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][0] = dp[i - 1][1];	
	} 
	cout << dp[n][1] + dp[n][0];
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int dp[N][N][N];
//dp[i][j][k]
//表示在s的前i个字符 删除k个'('的情况下 可以和 t的前j个字符匹配
//在dp[i][j][k] = 1时，一共有四种情况
/*
1、 s->'('; t->'('	
	k == 0，前面的字符串匹配：dp[i + 1][j + 1][k] = 1
	k != 0，前面的字符串不匹配：dp[i + 1][j][k + 1] = 1
2、 s->'('; t->')'  
 	这个(也是需要删除的 dp[i + 1][j][k + 1] = 1
3、 s->')'; t->')'
	k == 0，前面的字符串匹配：dp[i + 1][j + 1][k] = 1
	k != 0, 前面的字符串不匹配：dp[i + 1][j][k - 1] = 1
4、 s->')'; t->'('
	dp[i + 1][j][k - 1] = 1
*/ 
int main()
{
	string s, t;
	cin >> s >> t;
	s = " " + s, t = " " + t;
	int n = s.size() - 1, m = t.size() - 1;
	dp[0][0][0] = 1;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= m; j++)
			for(int k = 0; k <= n; k++)
				if(dp[i][j][k])
				{
					if(k == 0 && s[i + 1] == t[j + 1]) dp[i + 1][j + 1][k] = 1;//相等的情况 
					if(s[i + 1] == '(') dp[i + 1][j][k + 1] = 1;
					else if(s[i + 1] == ')' && k != 0) dp[i + 1][j][k - 1] = 1;
				}
	cout << (dp[n][m][0] ? "Possible" : "Impossible");		 
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 60, M = 1e5 + 5;
int n, t;
//v表示初始加分，d表示每分钟减的分，c表示解决第i道题需要的时间 
int f[M];
struct cf
{
	int v, d, c;
	bool operator <(const cf& x)
    {
        return x.d * c < d * x.c;//将写完这道题花费时间少的题目放在前面 
    }
}cf[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> t;
	for(int i = 1; i <= n; i++) cin >> cf[i].v;
	int sd = 0;
	for(int i = 1; i <= n; i++) cin >> cf[i].d, sd += cf[i].d;
	for(int i = 1; i <= n; i++) cin >> cf[i].c;
	sort(cf + 1, cf + n + 1);//要排序 
	for(int i = 1; i <= n; i++)
		for(int j = M - 1; j >= cf[i].c; j--)
			f[j] = max(f[j], f[j - cf[i].c] + cf[i].v - cf[i].d * j);
	int ans = - sd * M;
	for(int i = 0; i <= t; i++) ans = max(ans, f[i]);
	cout << ans;		
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, x, q;//表示共n个食堂，需要x份饭，罚款q 
const int N = 510;
struct s
{
	int a, b;//a表示菜的单价，b表示满b送一 
}s[N];
int f[N * 2];//表示打i份饭的最小花费 
int main()
{
	//初始化 
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	cin >> n >> x >> q;
	for(int i = 1; i <= n; i++) cin >> s[i].a >> s[i].b;
	for(int i = 1; i <= n; i++)
	{
		for(int j = n + x; j >= 1; j--)
		{
			for(int k = 0; k < s[i].b; k++)
			{
				if(j >= k) f[j] = min(f[j], f[j - k] + k * s[i].a);
				if(j >= s[i].b + 1) f[j] = min(f[j], f[j - s[i].b - 1] + s[i].b * s[i].a);  
			}	
		}	
	} 
	int ans = 0x3f3f3f3f;
	for(int i = n + x; i >= x; i--) ans = min(ans, f[i] + (i - x) * q);
	cout << ans;	
	return 0;
}