Espelhos binários

Time limit: 6000 msMemory limit: 256 MB

Uma fita de comprimento $n$ deve ser preenchida com os símbolos 0 e 1. Há $m$ exigências, cada uma sobre um intervalo fechado $[l,r]$ :

P: a leitura do intervalo da esquerda para a direita deve ser igual à leitura da direita para a esquerda.
A: a leitura da esquerda para a direita deve ser igual à leitura da direita para a esquerda depois de trocar todo 0 por 1 e todo 1 por 0.

Todas as exigências devem valer simultaneamente. Uma exigência A também se aplica ao símbolo central quando o intervalo tem tamanho ímpar.

Conte as fitas que satisfazem todas as exigências, módulo $10^9+7$ . Posições fora dos intervalos também fazem parte da fita e podem ser preenchidas livremente.

Input

A primeira linha contém $n$ e $m$ ( $1 \le n \le 200000$ , $0 \le m \le 200000$ ). Cada uma das próximas linhas contém , e um caractere ou (). Exigências repetidas são permitidas.

Output

Imprima o número de fitas válidas, módulo $10^9+7$ .

Samples

Sample 1

Input

4 2
1 4 A
1 3 P

Output

As fitas válidas são 0101 e 1010.

Sample 2

Input

3 1
1 3 A

Output

O símbolo central precisaria ser diferente de si mesmo.