N차원 여행

수빈이는 여행을 좋아한다. 지구에서 더 갈 곳이 없어진 수빈이는 N차원 우주로 여행을 떠났다. 이 우주의 점은 좌표 N개로 나타내고, 각 좌표에는 1부터 N까지 인덱스가 붙어 있다.

수빈이는 원점(모든 좌표가 0인 점)에서 출발하며, 한 번 움직일 때마다 다음 두 단계를 거친다.

• 움직일 좌표의 인덱스를 1부터 N 중에서 하나 고른다.
• 그 좌표의 값을 1 늘린 점이나 1 줄인 점으로 이동한다. 나머지 좌표는 이동 전과 같아야 한다.

수빈이는 떠나기 전에 여행 계획을 적어 두었다. 계획에는 이동마다 고른 좌표의 인덱스와, 그 좌표를 늘리는 방향으로 갔는지 줄이는 방향으로 갔는지가 순서대로 적혀 있다.

계획을 그대로 따라갔을 때 출발점과 마지막 점을 포함한 모든 점을 한 번씩만 방문하면 1을, 같은 점을 두 번 이상 방문하면 0을 출력하는 프로그램을 작성하시오.

첫째 줄에 차원의 수 $N$이 주어진다. ($1 \le N \le 10^9$)

둘째 줄에 여행 계획의 길이 $M$이 주어진다. ($1 \le M \le 50$)

셋째 줄에 계획에서 고른 좌표의 인덱스 $M$개가 이동 순서대로 공백으로 구분되어 주어진다. 각 인덱스는 $1$ 이상 $N$ 이하이다.

넷째 줄에 길이 $M$인 문자열이 주어진다. 이 문자열의 $i$번째 문자가 +이면 $i$번째 이동에서 좌표를 1 늘리고, -이면 1 줄인다.

모든 점을 한 번씩만 방문하면 1을, 아니면 0을 출력한다.

2차원에서 인덱스 1, 2, 1, 2를 고르고 방향이 차례로 +, +, -, -이면 $(0,0) \to (1,0) \to (1,1) \to (0,1) \to (0,0)$으로 움직여 $(0,0)$을 두 번 방문한다.

3차원에서 인덱스 1, 2, 3, 1, 2를 고르고 방향이 차례로 +, +, +, -, -이면 $(0,0,0) \to (1,0,0) \to (1,1,0) \to (1,1,1) \to (0,1,1) \to (0,0,1)$으로 움직여 어떤 점도 두 번 방문하지 않는다.