Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Number of Subsequences

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string $$$s$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $$$s$$$ be $$$k$$$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $$$3^{k}$$$ possible strings consisting only of letters "a", "b" and "c". For example, if $$$s = $$$"ac?b?c" then we can obtain the following strings: $$$[$$$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$$$]$$$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $$$10^{9} + 7$$$.

A subsequence of the string $$$t$$$ is such a sequence that can be derived from the string $$$t$$$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $$$(2, 5, 6)$$$ and a subsequence consisting of letters at positions $$$(3, 5, 6)$$$.

Input

The first line of the input contains one integer $$$n$$$ $$$(3 \le n \le 200\,000)$$$ — the length of $$$s$$$.

The second line of the input contains the string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".

Output

Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $$$10^{9} + 7$$$.

Examples

Input

6 ac?b?c

Output

24

Input

7 ???????

Output

2835

Input

9 cccbbbaaa

Output

0

Input

5 a???c

Output

46

Note

In the first example, we can obtain $$$9$$$ strings:

- "acabac" — there are $$$2$$$ subsequences "abc",
- "acabbc" — there are $$$4$$$ subsequences "abc",
- "acabcc" — there are $$$4$$$ subsequences "abc",
- "acbbac" — there are $$$2$$$ subsequences "abc",
- "acbbbc" — there are $$$3$$$ subsequences "abc",
- "acbbcc" — there are $$$4$$$ subsequences "abc",
- "accbac" — there is $$$1$$$ subsequence "abc",
- "accbbc" — there are $$$2$$$ subsequences "abc",
- "accbcc" — there are $$$2$$$ subsequences "abc".

So, there are $$$2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$$$ subsequences "abc" in total.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2022 18:14:23 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|