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

放灯时要遵守下列规则：

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

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

例如：N=8（格子数）

           R=2 （红灯数）

           B=3 （蓝灯数）

放置的方法有：

R-B顺序

B-R顺序

放置的总数为12种。

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

输入数据有若干行；

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

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

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

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

NOIP