[백준] 26156번 나락도 락이다 (gold 3

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        //나누는 수
        int div=1000000007;
        int n=Integer.valueOf(br.readLine());
        //조합 R 앞에 있는 문자의 조합 * rock가짓수
        long[] num=new long[1000001];
        num[1]=1;
        for(int i=2; i<num.length; i++){
            num[i]=(2*num[i-1]+1)%(div);
        }

        //뒤에서 부터 해당 문자가 추가 될 때마다, +해줌
        //k일때는 k에 +1;
        //c이면, 현재 k상태만큼 c의 가짓수가 증가하므로 c+k,
        //o도 동일하다.
        //r일때는 문자의 맨 앞이므로, 가짓 수 계산해서 연산한다. 
        long k=0;
        long c=0;
        long o=0;
        long r=0;

        long answer=0;
        String a=br.readLine();
        for(int i=a.length()-1; i>=0; i--){
            if(a.charAt(i)=='K'){
                k=(k+1)%div;
            }
            else if(a.charAt(i)=='C'){
                c=(c+k)%div;
            }
            else if(a.charAt(i)=='O'){
                o=(o+c)%div;
            }
            //R일때 맨 앞자리면, 그냥 o가짓수만큼 더하기.
            else if(a.charAt(i)=='R'){
                if(i==0){
                    answer= (answer+o)%div;
                }
                //만약 앞에 다른 문자들이 있으면,
                //그 조합만큼 더 만들 수 있다.
                //따라서 이경우는 o로 만들 수 있는 가짓수에 r붙인거 뿐만 아니라,
                //앞자리 갯수의 조합에 의한 경우. (o가 0이면 없으므로 더하면 안됨.
                else if(o!=0){
                    answer= (answer+(o*(num[i]+1)%div))%div;
                }
            }

        }

        bw.write(answer+"");
        bw.flush();
    }
}