2372: 交通序列号
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：3
题目描述
在一条笔直的道路上共有N个路口，每个路口处都有关于该条道路的通行的信号灯。
显然，信号灯共有绿(G)、红(R)、黄(Y)三种颜色。
交通部门指出，当绿色信号灯为奇数个，且红色信号灯为偶数个时，该条道路为“通畅的”。
现在交给你一个任务：给定从第一个路口到最后一个路口的所有信号灯的序列，计算出这个序列在“通畅的”道路的字典序中的序号。
输入
第一行，正整数N (N <= 10^5)；
第二行，一个长度为N的序列(不含空格)，其中第i个字母表示第i个路口信号灯的状态。
输出
输出这个序列在“通畅的”道路的字典序中的序号
(由于答案可能比较大，所以你只要输出答案除12345的余数即可。
注意，若此道路不通畅，请输出"invalid"[不含双引号])
样例输入 复制
4
RGYR
样例输出 复制
9提示
【样例说明】
这20种通畅道路分别是（按字典序，此部分无须输出）
GGGY、GGYG、GRRY、GRYR、GYGG、
GYRR、GYYY、RGRY、RGYR、RRGY、
RRYG、RYGR、RYRG、YGGG、YGRR、
YGYY、YRGR、YRRG、YYGY、YYYG
【数据规模】
对于40%的数据，N<=15；
对于70%的数据，N<=10^4;
对于100%的数据，N<=10^5。