Rankings

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

There are n teams (labelled from 1 to n) who take part in a programming competition every year, and at the end they are ranked in order of merit. The rankings for last year are known. This year, the jury wants to make the event less competitive, and decides not to publish such a ranking list (since teams near the bottom might get disheartened).

You want to know the rankings for this year. You ask every team the difference between this year’s ranking and last year’s ranking. Some teams will tell you the accurate difference. But some teams just tell you their rank are great or less than last year. Their answer can be marked as : “x”,”+”,”-”。 “x” means the accurate difference between this year’s ranking and last year’s ranking. “+” means this year’s ranking is greater than last year’s. “-” means this year’s ranking is less than last year’s. For example, one team’s ranking of last year is 1, this year’s ranking is 3, this team may tell you “2”, or “+”. And if one team’s ranking of last year is 5, this year’s ranking is 2, this team may tell you “-3” or “-”. x can be positive , negative or zero.

Given last year's rankings and every team’s answers. You should calculate the number of impossible ranks. It is possible that some teams tell lies, you should also detect this.

Input

There are multiple test cases. The first line of each test case is an integer N(1<=N<=1000), which indicates the number of teams.

The following one line with n integers ti (1 ≤ ti ≤ N): the rankings for last year, from best team to worst team. ti represents the team who came in position i (1-indexed) on the ranklist. All the ti will be distinct.

The following N lines is the answers of every team. The i-th is the i-th team’s answer, it can be a number x or “+”, “-”.

All teams rankings will be distinct. So the ranking list will be a permutation of 1 to N.

Output

If there isn’t any possible ranking list for this year, please output  "IMPOSSIBLE",else output number of possible orderings modulo 2014.

Sample Input

5
2 1 3 5 4
1
+
-
-
0
3
1 2 3
+
+
+

Sample Output

2
IMPOSSIBLE

Source

kuangbin

Manager

Information
Solved Number15
Submit Number60
Problem Tags
brute force
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel