暂无测试数据。

设在一排上有 $n$ 个格子（$n\le20$），若在格子中放置有不同颜色的灯，每种灯的个数记为 $n_1,n_2,\cdots n_k$（$k$ 表示不同颜色灯的个数）。 放灯时要遵守下列规则：

1. 同一种颜色的灯不能分开；
2. 不同颜色的灯之间至少要有一个空位置。

输入格式

第一行：一个整数 $n$。

第 $2\cdots k+1$ 行：每行一个大写字母和一个整数 $n_i$（$i=1\cdots k$），表示灯的颜色和这种颜色灯的个数。

第 $k+2$ 行：Q（结束标记，Q 本身不是灯的颜色）

输出格式

输出只有一行，排列总数。

8
R 2
B 3
Q

12