Đếm xâu con

Cho một xâu kí tự \(s\) chứa các kí tự "a", "b", "c", và "?".

Gọi số lượng kí tự "?" trong xâu \(s\) là \(k\). Mỗi dấu "?" trong xâu ta có thể thay thế bằng \(1\) trong \(3\) kí tự "a", "b", "c". Như vậy, có thể tạo ra \(3^k\) xâu chỉ chứa các kí tự "a", "b", "c". Ví dụ, xâu \(s\) = "ac?b?c" ta có thể tạo ra được \(9\) xâu ["acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"].

Yêu cầu: Đếm tất cả các xâu con "abc" xuất hiện trong tất cả các xâu có thể tạo ra. In ra kết quả theo modulo \(10^9 + 7\).

Nhắc lại: Xâu con là xâu có thể thu được bằng cách xóa các kí tự ở một số các vị trí trong xâu. Xâu con của xâu "abc" là: ["", "a", "b", "c", "ab", "ac", "bc", "abc"].

Input

Dòng đầu tiên là số nguyên dương \(n\) - độ dài xâu \(s\).

Dòng thứ hai là xâu \(s\) chỉ chứa các kí tự "a", "b", "c", "?".

Output

Kết quả bài toán.

Example

6
ac?b?c

24

Scoring

\(20\%\) số test có \(n \leq 10\).

\(20\%\) số test có \(n \leq 50\).

\(20\%\) số test có \(n \leq 1000\).

\(20\%\) số test đảm bảo xâu \(s\) không có kí tự "?" nào.

\(20\%\) số test cos \(n \leq 200000\).