#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x>S; L=S.size(); ZERO(dp); int ma=0; dp[0][0][0][0][0][0]=1; FOR(i,L) { int cur=i%2,tar=cur^1; memmove(dp[tar],dp[cur],sizeof(dp[tar])); for(a=0;a*5<=i;a++) for(b=0;a*5+b*4<=i;b++) for(c=0;a*5+b*4+c*3<=i;c++) for(d=0;a*5+b*4+c*3+d*2<=i;d++) for(e=0;a*5+b*4+c*3+d*2+e<=i;e++) if(dp[cur][a][b][c][d][e]) { if(S[i]=='K' || S[i]=='?') if(e<20) dp[tar][a][b][c][d][e+1] = 1; if(S[i]=='U' || S[i]=='?') if(d<20 && e) dp[tar][a][b][c][d+1][e-1] = 1; if(S[i]=='R' || S[i]=='?') if(c<20 && d) dp[tar][a][b][c+1][d-1][e] = 1; if(S[i]=='O' || S[i]=='?') if(b<20 && c) dp[tar][a][b+1][c-1][d][e] = 1; if(S[i]=='I' || S[i]=='?') if(a<20 && b) dp[tar][a+1][b-1][c][d][e] = 1, ma=max(ma,a+1); } } cout<