問題一覧 > 通常問題

No.1996 <><

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : MasKoaTSMasKoaTS / テスター : ShirotsumeShirotsume potato167potato167
2 ProblemId : 7525 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-29 14:51:30

問題文

長さ $N$ の正整数列 $A = \{ A_{1}, A_{2}, \dots, A_{N} \}$ と長さ $K$ の不等号列 $s = \{ s_{1}, s_{2}, \dots, s_{K} \}$ が与えられます。

$1 \leq x_{1} < x_{2} < \cdots < x_{K+1} \leq N$ を満たす整数の組 $(x_{1}, x_{2}, \dots, x_{K+1})$ を選ぶ方法であって、
$i = 1, 2, \dots, K$ すべてに対して次の $2$ つの条件をともに満たすものの個数を求めてください。

  • $s_{i}$ が < ならば $A_{x_{i} } < A_{x_{i+1} }$

  • $s_{i}$ が > ならば $A_{x_{i} } > A_{x_{i+1} }$

ただし、答えは非常に大きくなる可能性があるので、$10^{9}+7$ で割った余りを出力してください。

制約

  • $1 \leq K < N \leq 1500$

  • $1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

  • $N$, $K$ 及び $A_{i}$ $(1 \leq i \leq N)$ はすべて整数

  • $s_{i}$ $(1 \leq i \leq K)$ は <, > のうちいずれか $1$ 文字

入力

入力は次の形式で与えられます。

$N$ $K$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
$s_{1} s_{2} \cdots s_{K}$
  • $1$ 行目には $N$, $K$ がこの順に半角スペース区切りで与えられる

  • $2$ 行目には $A_{1}, A_{2}, \dots, A_{N}$ がこの順に半角スペース区切りで与えられる

  • $3$ 行目には $s_{1}, s_{2}, \dots, s_{K}$ がこの順に長さ $K$ の文字列として与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
5 3
2 3 1 1 4
<><
出力
2

条件を満たす組は $(x_{1}, x_{2}, x_{3}, x_{4}) = (1,2,3,5), (1,2,4,5)$ の $2$ 個です。

例えば $(x_{1}, x_{2}, x_{3}, x_{4}) = (1,2,4,5)$ のとき、$(A_{1}, A_{2}, A_{4}, A_{5} ) = (2,3,1,4)$ は $3$ 個の不等式

  • $2 < 3$

  • $3 > 1$

  • $1 < 4$

をすべて満たします。

サンプル2
入力
6 4
1 1 2 5 1 4
>><<
出力
0

条件を満たす整数の組は存在しません。

サンプル3
入力
20 5
13359410 197769 10910581 3 512 5732 9026607 22294 3997084 262110309 51421 728930621 353629015 49 1907 208452 13 13760365 6779710 3484117
><><<
出力
1744
サンプル4
入力
40 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
<<<<<<<<<<<<<<<<<<<
出力
846527861

条件を満たす整数の組の個数を $10^{9} + 7$ で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。