Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters and ?.

$S$ has $2^{N}-1$ non-empty subsequences. Among them, we define a good subsequence as one that satisfies either of the following conditions.

Conditions

• The subsequence does not contain ?

• The subsequence contains exactly one ?

Here, let $T$ be the set of strings obtained by choosing at most one character of the string yukicoder and replacing it with ?.

Find the number of good subsequences that are contained in $T$, modulo $10^9+7$.

Input

$N$
$S$

• The first line contains an integer $N$.

• The second line contains a string $S$.

Constraints

• $1≤N≤10^5$

• $N$ is an integer.

• $|S|=N$

• $S$ consists of lowercase English letters or ?.

Output

Print the answer on one line.

Print a newline at the end.

Sample

9
yukicoder

1

7
harurun

0

14
yukiyuki?coder

14