A - 119 × 2^23 + 1

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 300

問題文

AtCoder ではたびたび、次のような形式の問題が出題されています。

答えを 998244353 で割った余りを求めよ。

ところで、実は 998244353 = 119 \times 2^{23} + 1 という性質があります。それに関連して、次の問いに答えてください。

整数 N が与えられる。
N = a \times 2^b + c を満たす非負整数の組 (a, b, c) のうち、a + b + c が最小となるものにおける a + b + c の値を出力せよ。

制約

  • 1 \leq N \leq 10^{18}
  • N は整数

入力

入力は以下の形式で標準入力から与えられます。

N

出力

答えを出力してください。


入力例 1

998244353

出力例 1

143

998244353 = 119 \times 2^{23} + 1 であるため、(a, b, c) = (119, 23, 1) のとき等式 N = a \times 2^{b} + c が成り立ちます。
そのときの a+b+c の値は 143 です。
a+b+c \leq 142 となるような組は存在しないため、143 と出力すれば正解となります。


入力例 2

1000000007

出力例 2

49483

1000000007 = 30517 \times 2^{15} + 18951 であるため、(a, b, c) = (30517, 15, 18951) のとき等式 N = a \times 2^{b} + c が成り立ちます。
そのときの a+b+c の値は 49483 です。
a+b+c \leq 49482 となるような組は存在しないため、49483 と出力すれば正解となります。


入力例 3

1

出力例 3

1

2^0 = 1 であることに注意してください。


入力例 4

998984374864432412

出力例 4

2003450165

Score: 300 points

Problem Statement

In problems on AtCoder, you are often asked to:

find the answer modulo 998244353.

Here, we have 998244353 = 119 \times 2^{23} + 1. Related to this, solve the following prolem:

You are given an integer N.
Print the minimum possible value of a + b + c for a triple of non-negative integers (a, b, c) satisfying N = a \times 2^b + c.

Constraints

  • 1 \leq N \leq 10^{18}
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

998244353

Sample Output 1

143

We have 998244353 = 119 \times 2^{23} + 1, in other words, the triple (a, b, c) = (119, 23, 1) satisfies N = a \times 2^{b} + c.
The value a+b+c for this triple is 143.
There is no such triple where a+b+c \leq 142, so 143 is the correct output.


Sample Input 2

1000000007

Sample Output 2

49483

We have 1000000007 = 30517 \times 2^{15} + 18951, in other words, the triple (a, b, c) = (30517, 15, 18951) satisfies N = a \times 2^{b} + c.
The value a+b+c for this triple is 49483.
There is no such triple where a+b+c \leq 49482, so 49483 is the correct output.


Sample Input 3

1

Sample Output 3

1

Note that we have 2^0 = 1.


Sample Input 4

998984374864432412

Sample Output 4

2003450165
B - Electric Board

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 500

問題文

いま、電光掲示板に 01 から成る長さ N の文字列 S が表示されています。

あなたは次の操作を何回でも行うことができます。なお、ここでは電光掲示板に表示されている文字列の i (1 \leq i \leq N) 文字目を S_i と表します。

操作 整数 (l, r) (1 \leq l < r \leq N) であって、次の条件のうちいずれかを満たすものを 1 組選び、S_lS_r を入れ替える。

  • S_l= 0 かつ S_{l+1}=\cdots=S_r= 1 を満たす。
  • S_{l}=\cdots=S_{r-1}= 1 かつ S_r= 0 を満たす。

電光掲示板に表示されている文字列を T に一致させることができるか判定し、可能な場合は操作回数として考えられる最小の値を求めてください。

制約

  • 2 \leq N \leq 500000
  • S01 からなる長さ N の文字列である
  • T01 からなる長さ N の文字列である

入力

入力は以下の形式で標準入力から与えられます。

N
S
T

出力

電光掲示板に表示されている文字列を T にすることが不可能な場合は、-1 を出力してください。

可能な場合は、操作回数として考えられる最小の値を出力してください。


入力例 1

7
1110110
1010111

出力例 1

2

例えば以下のように操作を行えば、2 回の操作で電光掲示板に表示されている文字列を 1010111 にすることができます。

  • (l, r) = (2, 4) を選んで操作を行う。そのとき、電光掲示板の文字列は 1110110 から 1011110 に変化する。
  • (l, r) = (4, 7) を選んで操作を行う。そのとき、電光掲示板の文字列は 1011110 から 1010111 に変化する。

入力例 2

20
11111000000000011111
11111000000000011111

出力例 2

0

操作を行う前の時点で、電光掲示板に表示されている文字列が T であるため、答えは 0 となります。


入力例 3

6
111100
111000

出力例 3

-1

どのように操作を行っても、電光掲示板に文字列 T を表示させることが不可能な場合は、-1 と出力してください。


入力例 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

出力例 4

22

Score: 500 points

Problem Statement

An electric bulletin board is showing a string S of length N consisting of 0 and 1.

You can do the following operation any number of times, where S_i denotes the i-th character (1 \leq i \leq N) of the string shown in the board.

Operation: choose a pair of integers (l, r) (1 \leq l < r \leq N) satisfying one of the conditions below, and swap S_l and S_r.

  • S_l= 0 and S_{l+1}=\cdots=S_r= 1.
  • S_{l}=\cdots=S_{r-1}= 1 and S_r= 0.

Determine whether it is possible to make the string shown in the board match T, and find the minimum number of operations needed if it is possible.

Constraints

  • 2 \leq N \leq 500000
  • S is a string of length N consisting of 0 and 1.
  • T is a string of length N consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

N
S
T

Output

If it is impossible to make the board show the string T, print -1.

If it is possible, find the minimum number of operations needed.


Sample Input 1

7
1110110
1010111

Sample Output 1

2

Here is one possible way to make the board show the string 1010111 in two operations:

  • Do the operation with (l, r) = (2, 4), changing the string in the board from 1110110 to 1011110.
  • Do the operation with (l, r) = (4, 7), changing the string in the board from 1011110 to 1010111.

Sample Input 2

20
11111000000000011111
11111000000000011111

Sample Output 2

0

The board already shows the string T before doing any operation, so the answer is 0.


Sample Input 3

6
111100
111000

Sample Output 3

-1

If there is no sequence of operations that makes the board show the string T, print -1.


Sample Input 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

Sample Output 4

22
C - ARC Wrecker 2

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 500

問題文

AtCoder 街道には N 棟のビルが建っており、西から順に 1 から N までの番号が付けられています。最初の時点では、ビルの高さはそれぞれ A_1, A_2, \dots, A_N です。

ARC 解体業者の社長である高橋君は、整数 l, r (1 \leq l \lt r \leq N) を選び、ビル l, l+1, \dots, r の高さをすべて 0 にしようと計画しています。この際に、以下の 2 種類の操作を好きな順番で何回でも行うことができます。

  • 整数 x (l \leq x \leq r-1) を決めて、ビル x・ビル x+1 の高さを 1 ずつ増やす
  • 整数 x (l \leq x \leq r-1) を決めて、ビル x・ビル x+1 の高さを 1 ずつ減らす(この操作は両方のビルの高さが 1 以上のときのみ可能)

選べる x の範囲が (l,r) に依存することに注意してください。

高橋君が計画を達成することが可能な (l, r) の選び方は何通りあるでしょうか?

制約

  • 2 \leq N \leq 300000
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N
A_1 A_2 \cdots A_N

出力

答えを出力してください。


入力例 1

5
5 8 8 6 6

出力例 1

3

(l, r) = (2, 3), (4, 5), (2, 5) については、高橋君は目的を達成することができます。

例えば、(l, r) = (2, 5) と選ぶとき、例えば以下の順に操作を行うことで、ビル 2, 3, 4, 5 の高さを 0 にできます。

  • 「ビル 4, 5 の高さを 1 ずつ減らす」操作を 6 回続けて行う
  • 「ビル 2, 3 の高さを 1 ずつ減らす」操作を 8 回続けて行う

残り 7 種類の (l, r) の選び方については、どのような操作の手順をとっても、高橋君は目的を達成することができません。


入力例 2

7
12 8 11 3 3 13 2

出力例 2

3

(l, r) = (2, 4), (3, 7), (4, 5) については、高橋君は目的を達成することができます。

例えば、(l, r) = (3, 7) と選ぶとき、以下の図のように操作を行うことが考えられます。


入力例 3

10
8 6 3 9 5 4 7 2 1 10

出力例 3

1

高橋君が目的を達成できるのは、(l, r) = (3, 8) のときしかありません。


入力例 4

14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

出力例 4

8

Score: 500 points

Problem Statement

There are N buildings along the AtCoder Street, numbered 1 through N from west to east. Initially, Buildings 1, 2, \ldots, N have the heights of A_1, A_2, \dots, A_N, respectively.

Takahashi, the president of ARC Wrecker, Inc., plans to choose integers l and r (1 \leq l \lt r \leq N) and make the heights of Buildings l, l+1, \dots, r all zero. To do so, he can use the following two kinds of operations any number of times in any order:

  • Set an integer x (l \leq x \leq r-1) and increase the heights of Buildings x and x+1 by 1 each.
  • Set an integer x (l \leq x \leq r-1) and decrease the heights of Buildings x and x+1 by 1 each. This operation can only be done when both of those buildings have heights of 1 or greater.

Note that the range of x depends on (l,r).

How many choices of (l, r) are there where Takahashi can realize his plan?

Constraints

  • 2 \leq N \leq 300000
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.


Sample Input 1

5
5 8 8 6 6

Sample Output 1

3

Takahashi can realize his plan for (l, r) = (2, 3), (4, 5), (2, 5).

For example, for (l, r) = (2, 5), the following sequence of operations make the heights of Buildings 2, 3, 4, 5 all zero.

  • Decrease the heights of Buildings 4 and 5 by 1 each, six times in a row.
  • Decrease the heights of Buildings 2 and 3 by 1 each, eight times in a row.

For the remaining seven choices of (l, r), there is no sequence of operations that can realize his plan.


Sample Input 2

7
12 8 11 3 3 13 2

Sample Output 2

3

Takahashi can realize his plan for (l, r) = (2, 4), (3, 7), (4, 5).

For example, for (l, r) = (3, 7), the following figure shows one possible solution.


Sample Input 3

10
8 6 3 9 5 4 7 2 1 10

Sample Output 3

1

Takahashi can realize his plan for (l, r) = (3, 8) only.


Sample Input 4

14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

Sample Output 4

8
D - Grid Repainting 3

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 700

問題文

HW 列のマス目で表されるキャンバスがあり、上から i (1 \leq i \leq H) 行目・左から j (1 \leq j \leq W) 列目のマスを (i, j) と表します。最初、マス (i, j)s_{i, j}= R のとき赤色で、s_{i, j}= B のとき青色で塗られています。

あなたは「次の 2 つのうち一方を選んで操作すること」を何回でも行うことができます。

操作X 赤色で塗られているマスを 1 つ選び、そのマスと同じ行にあるすべてのマス(自分自身を含む)を白色に塗り替える。
操作Y 赤色で塗られているマスを 1 つ選び、そのマスと同じ列にあるすべてのマス(自分自身を含む)を白色に塗り替える。

最終的に白色で塗られたマスの個数を最大にするような、操作手順の一例を示してください。

制約

  • 1 \leq H \leq 2500
  • 1 \leq W \leq 2500
  • s_{i, j}R または B である (1 \leq i \leq H, 1 \leq j \leq W)
  • H, W は整数

入力

入力は以下の形式で標準入力から与えられます。

H W
s_{1, 1}s_{1, 2}s_{1, 3}\cdotss_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3}\cdotss_{2, W}
s_{3, 1}s_{3, 2}s_{3, 3}\cdotss_{3, W}
 \vdots
s_{H, 1}s_{H, 2}s_{H, 3}\cdotss_{H, W}

出力

以下の形式で、標準出力に出力してください。

n
t_1 r_1 c_1
t_2 r_2 c_2
t_3 r_3 c_3
 \vdots
t_n r_n c_n

ここで、n は操作を行う回数、t_i, r_i, c_i (1 \leq i \leq n) は「i 回目にはマス (r_i, c_i) を選び操作 t_i を行うこと」を表しています。
t_iX または Y でなければなりません。
なお、複数通りの答えが考えられる場合は、そのどれを出力しても構いません。


入力例 1

4 4
RBBB
BBBB
BBBB
RBRB

出力例 1

3
X 1 1
Y 4 3
X 4 1

たとえば次のように操作を行うことで、10 個のマスを白色にすることができます。

  • まず、マス (1, 1) を選び、操作Xを行う。
  • 次に、マス (4, 3) を選び、操作Yを行う。
  • 次に、マス (4, 1) を選び、操作Xを行う。

なお、11 個以上のマスを白色にする方法は存在しません。


入力例 2

1 119
BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB

出力例 2

4
Y 1 60
Y 1 109
Y 1 46
X 1 11

すべてのマスを白色に塗り替えることができます。


入力例 3

10 10
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

出力例 3

0

赤色のマスが 1 つも存在しないため、そもそも操作を行うことができません。

Score: 700 points

Problem Statement

We have a canvas represented as a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W). Initially, (i, j) is painted red if s_{i, j}= R and blue if s_{i, j}= B.

For any number of times, you can choose one of the two operations below and do it.

Operation X: Choose a square painted red, and repaint all squares in the row containing that square (including itself) white.
Operation Y: Choose a square painted red, and repaint all squares in the column containing that square (including itself) white.

Show one way that maximizes the number of squares painted white in the end.

Constraints

  • 1 \leq H \leq 2500
  • 1 \leq W \leq 2500
  • s_{i, j} is R or B. (1 \leq i \leq H, 1 \leq j \leq W)
  • H and W are integers.

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3}\cdotss_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3}\cdotss_{2, W}
s_{3, 1}s_{3, 2}s_{3, 3}\cdotss_{3, W}
 \vdots
s_{H, 1}s_{H, 2}s_{H, 3}\cdotss_{H, W}

Output

Print the following to Standard Output:

n
t_1 r_1 c_1
t_2 r_2 c_2
t_3 r_3 c_3
 \vdots
t_n r_n c_n

Here, n is the number of operations you do, and t_i, r_i, c_i means that your i-th operation is Operation t_i with (r_i, c_i) being chosen, where t_i is X or Y.
If there are multiple possible solutions, you may print any of them.


Sample Input 1

4 4
RBBB
BBBB
BBBB
RBRB

Sample Output 1

3
X 1 1
Y 4 3
X 4 1

Here is one sequence of operations that makes 10 squares white:

  • First, do Operation X choosing (1, 1).
  • Then, do Operation Y choosing (4, 3).
  • Then, do Operation X choosing (4, 1).

There is no way to make 11 or more squares white.


Sample Input 2

1 119
BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB

Sample Output 2

4
Y 1 60
Y 1 109
Y 1 46
X 1 11

We can repaint all squares white.


Sample Input 3

10 10
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

Sample Output 3

0

Since there is no red square, we cannot do the operations at all.

E - Pancakes

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 800

問題文

N 枚のパンケーキが積み重なった「パンケーキタワー」があります。最初、上から i 番目 (1 \leq i \leq N) のパンケーキの大きさは A_i です。シェフである高橋君は、このパンケーキタワーに対して次の操作を最大 1 回行うことができます。

  • 整数 l, r (1 \leq l \lt r \leq N) を選び、上から l, l+1, \dots, r 番目のパンケーキの並び方を反転させる。

ここで、見栄えの悪さを次のように定義するとき、操作後の見栄えの悪さとして考えられる最小の値を求めてください。

隣り合うパンケーキの大きさの差の総和。
すなわち、上から i 番目のパンケーキの大きさを A^{\prime}_i とするときの、|A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N| の値。

制約

  • 2 \leq N \leq 300000
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N
A_1 A_2 \cdots A_N

出力

見栄えの悪さとして考えられる最小の値を出力してください。


入力例 1

5
7 14 12 2 6

出力例 1

17

l = 2, r = 5 を選んで操作をすると、操作後のパンケーキの大きさは上から順に 7, 6, 2, 12, 14 となります。

このときの見栄えの悪さは |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17 です。これが最小値となり、他のどんな方法を使ってもこれより見栄えの悪さを小さくすることはできません。


入力例 2

3
111 119 999

出力例 2

888

この入力例では、操作をしないことで見栄えの悪さを最小にすることができます。

このとき、パンケーキの大きさは上から順に 111, 119, 999 となり、見栄えの悪さは |111-119| + |119-999| = 8 + 880 = 888 となります。


入力例 3

6
12 15 3 4 15 7

出力例 3

19

l = 3, r = 5 を選んで操作をすると、操作後のパンケーキの大きさは上から順に 12, 15, 15, 4, 3, 7 となります。

このときの見栄えの悪さは |12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19 で、これが最小値となります。


入力例 4

7
100 800 500 400 900 300 700

出力例 4

1800

l = 2, r = 4 を選んで操作をすると、操作後のパンケーキの大きさは上から順に 100, 400, 500, 800, 900, 300, 700 となり、このときの見栄えの悪さは 1800 となります。


入力例 5

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

出力例 5

2576376600

Score: 800 points

Problem Statement

We have a pancake tower which is a pile of N pancakes. Initially, the i-th pancake from the top (1 \leq i \leq N) has a size of A_i. Takahashi, a chef, can do the following operation at most once.

  • Choose integers l and r (1 \leq l \lt r \leq N) and turn the l-th through r-th pancakes upside down, reversing the order.

Find the minimum possible ugliness of the tower after the operation is done (or not), defined below:

the ugliness is the sum of the differences of the sizes of adjacent pancakes;
that is, the value |A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N|, where A^{\prime}_i is the size of the i-th pancake from the top.

Constraints

  • 2 \leq N \leq 300000
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the minimum possible ugliness of the tower.


Sample Input 1

5
7 14 12 2 6

Sample Output 1

17

If we do the operation choosing l = 2 and r = 5, the pancakes will have the sizes of 7, 6, 2, 12, 14 from top to bottom.

The ugliness here is |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17. This is the minimum value possible; there is no way to achieve less ugliness.


Sample Input 2

3
111 119 999

Sample Output 2

888

In this sample, not doing the operation minimizes the ugliness.

In that case, the pancakes will have the sizes of 111, 119, 999 from top to bottom, for the ugliness of |111-119| + |119-999| = 8 + 880 = 888.


Sample Input 3

6
12 15 3 4 15 7

Sample Output 3

19

If we do the operation choosing l = 3 and r = 5, the pancakes will have the sizes of 12, 15, 15, 4, 3, 7 from top to bottom.

The ugliness here is |12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19, which is the minimum value possible.


Sample Input 4

7
100 800 500 400 900 300 700

Sample Output 4

1800

If we do the operation choosing l = 2 and r = 4, the pancakes will have the sizes of 100, 400, 500, 800, 900, 300, 700 from top to bottom, for the ugliness of 1800.


Sample Input 5

10
535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725

Sample Output 5

2576376600
F - AtCoder Express 3

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点: 800

問題文

AtCoder 鉄道には N+1 個の駅があり、駅には 0 から N までの番号が付けられています。ここではかつて、各 i (0 \leq i \leq N-1) に対して駅 i と駅 i+1 の間を双方向に 1 分で走行する 普通列車 のみが運行されていました。

しかし、ある日鉄道会社は「光速派」と「準急派」の 2 つのグループに分裂し、駅 0 と駅 N を除く各駅は光速派と準急派のうち片方が管理することになりました。駅 j (1 \leq j \leq N-1) を管理するグループは文字 c_j で表され、A は光速派が、B は準急派が管理すること、? はまだ決まっていないことを表します。駅 0 と駅 N は重要な駅なので、両方が管理します。

ここで、光速派と準急派は、普通列車に加えて新たに 2 種類の鉄道路線を作ることにしました。

光速列車:光速派が管理する駅の番号を昇順に a_0, a_1, \dots, a_s として、各 k に対して駅 a_k と駅 a_{k+1} の間を双方向に 1 分で走行する。

準急列車:準急派が管理する駅の番号を昇順に b_0, b_1, \dots, b_t として、各 k に対して駅 b_k と駅 b_{k+1} の間を双方向に 1 分で走行する。

? の個数を q として、作られる鉄道路線は 2^q 通り考えられます。その中で、K 分以内の乗車で駅 0 から駅 N に行けるようになるものは何通りあるでしょうか?これを 10^9+7 で割った余りを求めてください。

制約

  • 2 \leq N \leq 4000
  • 1 \leq K \leq \frac{N+1}{2}
  • N, K は整数
  • c_1, c_2, \dots, c_{N-1} はそれぞれ AB? のいずれか

入力

入力は以下の形式で標準入力から与えられます。

N K
c_1c_2\cdotsc_{N-1}

出力

答えを 10^9+7 で割った余りを出力してください。


入力例 1

8 3
A??AB?B

出力例 1

4

ここでは 2^3 = 8 通りの鉄道路線がありえますが、そのうち以下の 4 通りについて、3 分以内の乗車で駅 0 から駅 8 に行くことが可能です。

  • 2, 3, 6 を光速派が管理する場合:駅 0 \rightarrow 5 \rightarrow 7 \rightarrow 8 と移動する(下図の #1 に対応)
  • 2, 3 を光速派が、駅 6 を準急派が管理する場合:駅 0 \rightarrow 5 \rightarrow 4 \rightarrow 8 と移動する(下図の #2 に対応)
  • 2 を光速派が、駅 3, 6 を準急派が管理する場合:駅 0 \rightarrow 3 \rightarrow 4 \rightarrow 8 と移動する(下図の #4 に対応)
  • 2, 3, 6 を準急派が管理する場合:駅 0 \rightarrow 1 \rightarrow 4 \rightarrow 8 と移動する(下図の #8 に対応)

したがって、答えは 4 通りとなります。これを図で表すと、以下のようになります。下図においては、赤色が光速派のみが管理する駅や光速列車の路線、青色が準急派のみが管理する駅や準急列車の路線を表すものとします。


入力例 2

11 6
???B??A???

出力例 2

256

ここでは、2^8 = 256 通りの組み合わせすべてについて、駅 0 から駅 11 まで 6 分以内の乗車で行くことが可能です。


入力例 3

16 5
?A?B?A?B?A?B?A?

出力例 3

10

以下の図に示される 10 通りの組み合わせについて、駅 0 から駅 16 まで 5 分以内の乗車で行くことが可能です。


入力例 4

119 15
????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????

出力例 4

313346281

条件を満たすものは 1623310324709451 通りありますが、これを 10^9 + 7 で割った余りである 313346281 を出力してください。

Score: 800 points

Problem Statement

There are N+1 stations along the AtCoder Line, numbered 0 through N. Formerly, it only had Local Trains, which run between Stations i and i + 1 in one minute in either direction for each i (0 \leq i \leq N-1).

One day, however, the railway company broke into two groups, called Ko-soku (light speed) and Jun-kyu (semi express). They decided that each station other than Stations 0 and N should be administered by one of the groups. The group that administers Station j (1 \leq j \leq N-1) is represented by a character c_j: A means that Ko-soku administers the station, B means Jun-kyu administers the station, and ? means it is undecided. Since Stations 0 and N are so important, both groups will administer them.

Now, Ko-soku and Jun-kyu have decided to run two new types of trains, in addition to the local trains.

Ko-soku Trains: Let Stations a_0, a_1, \dots, a_s be the stations administered by Ko-soku in ascending order. These trains run between Stations a_k and a_{k+1} in one minute in either direction for each k.

Jun-kyu Trains: Let Stations b_0, b_1, \dots, b_t be the stations administered by Jun-kyu in ascending order. These trains run between Stations b_k and b_{k+1} in one minute in either direction for each k.

There are 2^q ways in which these trains run, where q is the number of ?s. Among them, how many enables us to go from Station 0 to Station N in no more than K minutes' ride? Find this count modulo (10^9+7).

Constraints

  • 2 \leq N \leq 4000
  • 1 \leq K \leq \frac{N+1}{2}
  • N and K are integers.
  • Each of c_1, c_2, \dots, c_{N-1} is A, B, or ?.

Input

Input is given from Standard Input in the following format:

N K
c_1c_2\cdotsc_{N-1}

Output

Print the count modulo (10^9+7).


Sample Input 1

8 3
A??AB?B

Sample Output 1

4

Here, there are 2^3 = 8 possible ways in which the trains run. Among them, the following four enable us to go from Station 0 to Station 8 in no more than 3 minutes' ride.

  • If Ko-soku administers Stations 2, 3, 6, we can go Station 0 \rightarrow 5 \rightarrow 7 \rightarrow 8, as shown at #1 in the figure below.
  • If Ko-soku administers Stations 2, 3 and Jun-kyu administers Station 6, we can go Station 0 \rightarrow 5 \rightarrow 4 \rightarrow 8, as shown at #2 in the figure below.
  • If Ko-soku administers Station 2 and Jun-kyu administers Stations 3, 6, we can go Station 0 \rightarrow 3 \rightarrow 4 \rightarrow 8, as shown at #4 in the figure below.
  • If Jun-kyu administers Stations 2, 3, 6, we can go Station 0 \rightarrow 1 \rightarrow 4 \rightarrow 8, as shown at #8 in the figure below.

Therefore, the answer is 4. The figure below shows all the possible ways, where red stations and railways are administered only by Ko-soku, and blue stations and railways are administered only by Jun-kyu.


Sample Input 2

11 6
???B??A???

Sample Output 2

256

Here, all of the 2^8 = 256 ways enable us to go from Station 0 to Station 11 in no more than 6 minutes' ride.


Sample Input 3

16 5
?A?B?A?B?A?B?A?

Sample Output 3

10

10 ways shown in the figure below enable us to go from Station 0 to Station 16 in no more than 5 minutes' ride.


Sample Input 4

119 15
????????A?????????????????????????BA????????????????????????AB???????A???????????B?????????????????????????????A??????

Sample Output 4

313346281

There are 1623310324709451 desirable ways. Print this count modulo (10^9 + 7), that is, 313346281.