Có ~n~ biến nguyên ~x_1,x_2,\dots,x_n~. Ban đầu, với mọi cặp ~i < j~, hệ ràng buộc chứa bất đẳng thức ~x_i \le x_j~.

Bạn cần xử lý các thao tác sau:

• C i j: đảo chiều bất đẳng thức của đúng cặp ~i<j~. Nếu hiện tại là ~x_i \le x_j~ thì đổi thành ~x_i \ge x_j~, và ngược lại.</p>

• Q a b: đếm số cách gán cho mỗi biến một số nguyên trong đoạn ~[a,b]~ sao cho mọi bất đẳng thức hiện tại đều được thỏa mãn.

Kết quả của mỗi truy vấn loại Q được lấy modulo ~10^9+7~.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~q~ (~1 \le n,q \le 10^5~).

• Mỗi dòng trong ~q~ dòng tiếp theo mô tả một thao tác theo một trong hai dạng trên.

Với thao tác C, ~1 \le i<j \le n~. </p>

Với thao tác Q, ~0 \le a \le b \le 10^9~ và ~b-a \le 10^5~.

Output

Với mỗi thao tác Q, in ra trên một dòng đáp án tương ứng modulo ~10^9+7~.

Scoring

Sample Input 1

3 5
Q 0 1
C 1 3
Q 0 1
C 1 3
Q 1 3

Sample Output 1

4
2
10

Notes

Ban đầu cần chọn một bộ ba không giảm. Trên tập ~\{0,1\}~ có bốn bộ ba như vậy.

Sau khi đảo cặp ~(1,3)~, ta đồng thời có ~x_1 \le x_2 \le x_3~ và ~x_1 \ge x_3~, vì thế cả ba biến phải bằng nhau. Khi khôi phục bất đẳng thức ban đầu, số dãy không giảm độ dài ~3~ nhận giá trị trong ~\{1,2,3\}~ là ~10~.