Quang đố Trí một bài toán về tổ hợp trên chuỗi ký tự. Quang đưa cho Trí một chuỗi \(S\) độ dài \(n\) gồm các ký tự a, b, c và ?. Mỗi ký tự ? có thể được thay thế bằng một trong ba ký tự a, b hoặc c. Giả sử chuỗi \(S\) có \(k\) ký tự ?, Trí sẽ tạo ra được tổng cộng \(3^k\) chuỗi khác nhau chỉ gồm các ký tự a, b, và c.

Với mỗi chuỗi được tạo ra, ta xét số lượng "xâu con abc" – là những xâu con không liên tiếp có ba ký tự của nó nằm tại các chỉ số \((i, j, k)\) thỏa mãn: \(1 \leq i < j < k \leq n\) và \(S[i]=\) a, \(S[j]=\) b, \(S[k]=\) c.

Yêu cầu: Đếm số lượng "xâu con abc" trên tất cả các chuỗi có thể tạo ra từ \(S\). Do kết quả có thể rất lớn, hãy in ra kết quả chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa chuỗi ký tự \(S\).

Output

• Dòng duy nhất đưa ra kết quả tính được.

Example

6
ac?b?c

24

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 12\).
• Subtask \(2\) (\(20\%\) số điểm): xâu \(S\) không chứa ký tự ?.
• Subtask \(3\) (\(30\%\) số điểm): xâu \(S\) chỉ chứa ký tự ?.
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.