7005 - 灯的排列问题

通过次数

9

提交次数

16

时间限制 : 1 秒
内存限制 : 125 MB

设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N_1,N_2,……N_k(k表示不同颜色灯的个数)。

放灯时要遵守下列规则:

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

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

例如:N=8(格子数)

           R=2 (红灯数)

           B=3 (蓝灯数)

放置的方法有:

R-B顺序

15652644198835.png

B-R顺序

15652644703595.png

放置的总数为12种。

 

要求:请你根据给出的N,求出在N\times N个格子下的灯的排列总数。

输入

输入数据有若干行;

输入数据的第一行为一个整数N,表示N个格子;

接下来的每一行有一个字母P_i和一个数字N_i,分别表示灯的颜色和灯的数量,颜色和数量之间使用一个空格分隔;

最后一行为一个字母Q,为结束标记,Q本身并不是灯的颜色。

输出

输出数据为一行一个整数,代表灯的排列总数。

样例

输入

8
R 2
B 3
Q

输出

12

来源

NOIP