Limak có hai trạng thái cảm xúc là hạnh phúc hoặc buồn bã. Tâm trạng của cậu ấy có thể thay đổi (hoặc không) mỗi khi cậu ấy đọc một chữ cái Tiếng Anh in hoa. Chữ cái S và D sẽ làm cậu ấy buồn bã, chữ cái H sẽ làm cậu ấy hạnh phúc, và các nguyên âm (A, E, I, O, U) sẽ đảo ngược tâm trạng của cậu ấy. Những chữ cái khác sẽ không ảnh hưởng gì cả. Limak hiện đang hạnh phúc và cậu ấy muốn mình vẫn hạnh phúc sau khi đọc một xâu kí tự.

Bạn được cho một xâu ~s~ với ~n~ kí tự. Một kí tự hợp lệ trong xâu là một dấu chẩm hỏi ? hoặc một chữ cái Tiếng Anh in hoa từ A đến Z. Nếu như xâu có ~x~ dấu chấm hỏi thì sẽ có tổng cộng ~26^x~ cách thay chúng thành các chữ cái từ A đến Z. Nhiệm vụ của bạn là đếm số cách thay các dấu chẩm hỏi sao cho Limak sẽ hạnh phúc sau khi đọc xong xâu mới (ban đầu Limak đang hạnh phúc).

Ngoài ra, còn có ~q~ phép cập nhật, mỗi phép có dạng ~(i, c)~ thể hiện thao tác thay đổi kí tự thứ ~i~ trong xâu ~s~ thành kí tự ~c~. Bạn cần in ra đáp án với xâu ~s~ ban đầu trước khi bắt đầu cập nhật và sau mỗi phép cập nhật, chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \leq n, q \leq 200\:000)~ - độ dài của xâu ~s~ và số lượng phép cập nhật.

• Dòng thứ hai chứa xâu ~s~ ban đầu với ~n~ kí tự hợp lệ.

• Mỗi dòng trong số ~q~ dòng tiếp theo chứa một số nguyên ~i~ ~(1 \leq i \leq n)~ và một kí tự hợp lệ ~c~. Mỗi phép cập nhật sẽ thay đổi kí tự thứ ~i~ của xâu ~s~ thành kí tự ~c~. Không có phép cập nhật nào sẽ đổi một kí tự thành chính kí tự đó.

• Các kí tự trong xâu ~s~ được đánh số thứ tự từ ~1~ đến ~n~. Sau khi bạn thay đổi một kí tự, nó sẽ giữ nguyên cho tới khi nào nó bị thay đổi lần nữa (những phép cập nhật không phải là tạm thời).

Output

In ra ~q + 1~ dòng, mỗi dòng chứa đáp án ở thời điểm hiện tại, lấy số dư cho ~10^9 + 7~.

Sample Input

2 5
A?
2 O
1 H
1 ?
2 ?
2 H

Sample Output

6
1
0
7
403
26

Giải thích

Xâu ~s~ ban đầu là A? và sau các phép cập nhật lần lượt trở thành: AO, HO, ?O, ??, ?H.

Với xâu ban đầu A?, có tổng cộng ~6~ cách thay các dấu chấm hỏi để Limak cảm thấy hạnh phúc sau khi đọc hết xâu: AA, AE, AH, AI, AO, AU. Kí tự đầu tiên là một nguyên âm nên tâm trạng của Limak bị đảo ngược từ hạnh phúc sang buồn bã. Do đó, kí tự còn lại phải là một nguyên âm hoặc chữ cái H.