该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。

放灯时要遵守下列规则：

①同一种颜色的灯不能分开；

②不同颜色的灯之间至少要有一个空位置。

例如：N=8（格子数）

     R=2（红灯数）

     B=3（蓝灯数）

放置的方法有：

   R-B顺序

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

   B-R顺序

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

B

B

B

R

R

放置的总数为12种。

程序要求：求排列总数。

输入格式

数据输入的方式为：

N

P1（颜色，为一个字母） N1（灯的数量）

P2 N2

……

Q（结束标记，Q本身不是灯的颜色）

颜色和灯的数量之间由一个空格分隔。

输出格式

输出排列总数。

样例

8
R 2
B 3
Q

12