/*
我是一个习惯后悔，但是没办法忍受内疚感的二货==
这题是个无脑dp，但是比赛大概20min没出...其实最后5min我好好想想简单化边界条件，可以出的。
题意：
给你一个长度为1e6的由?*01四种字符组成的字符串，类似扫雷，?代表当前不确定，0代表当前无雷，并且
两边无雷，1代表当前五雷且两边有一个雷，2同样的，问当所有格子已知以后一共有多少种可能的局面。
思路：
首先想到的是，这个问题无后效性，而当前位置的合法方式只与它之前的两位有关。
所以dp的思路也是显而易见的，即dp[i][j]代表前i个最后两位的情况是j的时候的方案数。
其实最后两位的一共16种组合合法的方式只有9种。
注意：
也是我比赛被坑的地方，处理边界条件。
首先对于最后的两位是有要求的，例如最后一位不可能是2...(还有其他的情况)，答案即把最后两位合法的情况加起来。
然后dp一开始的第一位该如何办...
我比赛的时候想暴力写前两位的情况，然后dp后来发现这么写代码量...然后崩了....
然后刚想了想，其实我枚举第一位所有可能的情况就好。
因为合法的9种情况中有许多是等价的，我只需在其中选择一项使得dp[1][i]=1即可 ...
然后WA6...因为最后累加答案的时候忘记取模了...傻逼错误简直了==
*/
#include<bits/stdc++.h>
#define N 1000050
using namespace std;
long long dp[N][];
long long mod=1e9+;
char jilu[N];
inline void z(int a,int b,int i){
dp[i][a]+=dp[i-][b];
dp[i][a]%=mod;
}
long long ans=;
void ggg(int len)
{
for(int i=;i<=len;i++){
if(jilu[i]=='?'){
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
}
else if(jilu[i]==''){
z(,,i);
z(,,i);
z(,,i);
}
else if(jilu[i]==''){
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
}
else if(jilu[i]==''){
z(,,i);
z(,,i);
z(,,i);
}
else{
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
z(,,i);
}
}
ans+=dp[len][];
ans%=mod;
ans+=dp[len][];
ans%=mod;
ans+=dp[len][];
ans%=mod;
ans+=dp[len][];
ans%=mod;
ans+=dp[len][];
ans%=mod;
ans+=dp[len][];
ans%=mod;
}
int main()
{
scanf("%s",jilu+);
int len=strlen(jilu+);
if(len<){
if(jilu[]==''||jilu[]==''){
cout << <<endl;
}
else if(jilu[]=='?'){
cout << <<endl;
}
else{
cout << <<endl;
}
return ;
}
switch (jilu[]){
case '?':
dp[][]=;
dp[][]=;
dp[][]=;
break;
case '':
dp[][]=;
break;
case '':
dp[][]=;
break;
case '*':
dp[][]=;
}
ggg(len);
cout << ans <<endl;
}
