No submission language available for this problem.

Background

Special for beginners, ^_^

Description

设在一排上有 N 个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为 $N_1，N_2，……N_k$（表示不同颜色灯的个数，k < 4）。

放灯时要遵守下列规则：

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

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

例如：

N=8（格子数）

R=2（红灯数）

B=3（蓝灯数）

放置的方法有：

R-B 顺序

B-R 顺序

放置的总数为 12 种。

​程序要求：​求排列总数。

Format

Input

数据输入的方式为：

N

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

P2 N2

……

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

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

Output

输出排列总数。

Samples

8
R 2
B 3
Q

12

Limitation

1s, 1024KiB for each test case.