Số xâu con "abc"

Cho một xâu $s$ độ dài $n$ chỉ gồm các chữ cái thường "a", "b", "c" và dấu hỏi "?".

Gọi $k$ là số dấu hỏi trong $s$. Ta thay mỗi dấu hỏi bằng một trong ba chữ cái "a", "b" hoặc "c", qua đó thu được tất cả $3^k$ xâu chỉ gồm các chữ "a", "b", "c".

Với mỗi xâu $t$, một xâu con "abc" là một bộ ba vị trí $i<j<l$ sao cho $t_i=$ "a", $t_j=$ "b", $t_l=$ "c". Số xâu con "abc" của $t$ là số bộ ba vị trí như vậy.

Hãy tính tổng số xâu con "abc" trên tất cả $3^k$ xâu thu được. Vì kết quả có thể rất lớn, in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: độ dài xâu $s$.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các ký tự "a", "b", "c" và "?".

Dữ liệu ra

• In ra một số nguyên: tổng số xâu con "abc" trên tất cả các xâu thu được, theo modulo ${10}^9+7$.

Ràng buộc

• $3\le n\le 200000$

Ví dụ