덧셈 또는 곱셈

여동생이 숫자 블록과 연산자 블록으로 이루어진 나무 수학 장난감을 가지고 놀고 있다. 숫자 블록에는 1부터 9까지의 한 자리 숫자가 하나씩 적혀 있다. 연산자 블록은 양면이 있고, 각 면에 +와 ×가 적혀 있다.

여동생은 숫자 블록과 연산자 블록을 번갈아 나열해 식을 만들었다. 첫 블록은 숫자, 둘째는 연산자, 셋째는 숫자이며 이후도 같은 순서다. 여동생은 이 식의 값을 알 수 있겠느냐고 묻는다.

그다음 여동생은 아래 움직임 중 하나를 반복해서 한다.

• s $i$ $j$ (교환): $i$번째와 $j$번째 숫자 블록을 서로 바꾼다.
• f $i$ (뒤집기): $i$번째 연산자 블록을 뒤집는다. 연산자는 +와 ×가 번갈아 바뀐다.
• a (전체 뒤집기): 식에 있는 모든 연산자 블록을 뒤집는다.

움직임을 할 때마다 바뀐 식의 값을 바로 답해야 한다. 값이 이전과 같을 수도 있다. 곱셈은 덧셈보다 먼저 계산한다는 점을 기억한다.

첫 줄에 두 정수 $N$ ($2 \leq N \leq 2 \times 10^5$)과 $M$ ($1 \leq M \leq 2 \times 10^5$)이 주어진다. $N$은 정수의 개수이고, $M$은 질의의 개수이다.

둘째 줄에는 $2N - 1$개의 문자로 이루어진 초기 식이 주어진다. 홀수 번째 위치에는 1부터 9까지의 한 자리 숫자가, 짝수 번째 위치에는 연산자 + 또는 *가 온다.

이어지는 $M$개의 줄에는 여동생의 움직임이 하나씩 주어진다.

• 교환 움직임은 s $i$ $j$ 형태이며, $1 \leq i, j \leq N$이다. $i = j$이면 블록을 바꾸지 않는다.
• 뒤집기 움직임은 f $i$ 형태이며, $1 \leq i \leq N-1$이다. $i$번째 연산자를 뒤집는다.
• 전체 뒤집기 움직임은 a만으로 주어지며, 다른 값은 없다.

첫 줄에 초기 식의 값을 출력한다. 이어서 $M$개의 줄에 걸쳐 각 움직임 뒤의 값을 한 줄에 하나씩 출력한다. 값은 $10^9 + 7$로 나눈 나머지를 출력한다.