#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
LL MODVAL = 1000000007LL;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
LL POW(LL x, LL e) {
LL v = 1;
for(;e;x=MUL(x,x),e>>=1)
if(e&1)
v = MUL(v, x);
return v;
}
class IOIString { public:
string s;
LL nI, nQ;
int countIOIs(vector <string> mask)
{
s = accumulate( mask.begin(), mask.end(), string("") );
nI = count( s.begin(), s.end(), 'I' );
nQ = count( s.begin(), s.end(), '?' );
return SUB( POW(2,nQ), non_IOI() );
}
LL non_IOI()
{
LL ans = 0;
if( nI == 0 ) ans = ADD(ans, 1); // #I == 0
if( nI == 0 ) ans = ADD(ans, nQ); // #I == 1
if( nI == 1 ) ans = ADD(ans, 1); // #I == 1
for(int D=1; D<s.size(); D+=2)
for(int S=0; S<D; ++S)
ans = ADD(ans, non_IOI_2(S, D)); // #I >= 2
return ans;
}
LL non_IOI_2( int S, int D )
{
string t;
for(int i=S; i<s.size(); i+=D)
t += s[i];
// t 以外の部分は全部 'O' でないとダメ
if( count(t.begin(), t.end(), 'I') < nI )
return 0;
// t は /O*II+O*/ にマッチしないとダメ。4状態のオートマトンでDP
LL q0=1, q1=0, q2=0, q3=0;
for(int i=0; i<t.size(); ++i)
{
LL p0 = (t[i]=='O' ? q0 : t[i]=='I' ? 0 : q0);
LL p1 = (t[i]=='O' ? 0 : t[i]=='I' ? q0 : q0);
LL p2 = (t[i]=='O' ? 0 : t[i]=='I' ? ADD(q1,q2) : ADD(q1,q2));
LL p3 = (t[i]=='O' ? ADD(q2,q3) : t[i]=='I' ? 0 : ADD(q2,q3));
q0=p0, q1=p1, q2=p2, q3=p3;
}
return ADD(q2, q3);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, IOIString().countIOIs(mask));}
int main(){
CASE(0)
string mask_[] = {"IO?"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 1;
END
CASE(1)
string mask_[] = {"????"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 4;
END
CASE(2)
string mask_[] = {"?II"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 0;
END
CASE(3)
string mask_[] = {"I??O??I"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 16;
END
CASE(4)
string mask_[] = {"???I???????O???","???????????O??IO????????I???"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 438952513;
END
CASE(5)
string mask_[] = {"?"};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 0;
END
CASE(6)
string mask_[] = {
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
};
vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_));
int _ = 967087276;
END
}
// END CUT HERE