시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB511100.000%

문제

You have a one-dimensional puzzle. Every piece of the puzzle can be described by three values: length, type of the left border, and type of the right border. Borders can be one of three types: straight, convex, and concave. Pieces couldn't be reversed, i.e. you can't swap left and right borders of a piece. Any convex border can be connected with any concave border and vice versa. You can't connect pieces by two straight borders.

Figure 1: Example of pieces

You want to connect several (possibly one) pieces one after another in order to get a part of length $l$. The left and the right borders of the part should be straight. Find a number of sets of pieces, such that you can build desired part using all pieces from the set. The number could be large, so calculate it modulo $1\,000\,000\,007$. Note that you should find the number of sets of pieces, not the number of different ways of connecting them.

입력

The first line contains two integer numbers $n$ and $l$ --- the number of pieces and desired length of a part ($1 \le n \le 300$, $1 \le l \le 300$).

The following $n$ lines contain a description of the pieces. Every line contains $a_i$, $b_i$ and $c_i$ --- the length of the piece, type of its left border, and type of its right border, accordingly ($1 \le a_i \le l$; $b_i, c_i \in \{{\texttt{"in"}}, \texttt{"out"}, \texttt{"none"}\}$). String "in" denotes concave border, "out" --- convex, "none" --- straight.

출력

Output single integer --- the number of sets of pieces, such that you can build desired part using these pieces, modulo $1\,000\,000\,007$.

서브태스크

번호배점제한
120

$n \le 20$

220

$b_i \in \{\texttt{"in"}, \texttt{"none"}\}$, $c_i \in \{\texttt{"out"}, \texttt{"none"}\}$

320

$n, l \le 50$

420

$n, l \le 100$

520

No additional constraints

예제 입력 1

5 10
1 out out
6 none in
10 none none
4 out none
3 in none

예제 출력 1

3

예제 입력 2

4 5
1 none out
1 in out
2 in out
1 in none

예제 출력 2

1

힌트

Pieces of the puzzle from the first example correspond to the previous picture.

Figure 2: Sets of pieces, such that you can build desired part using them

채점 및 기타 정보

  • 예제는 채점하지 않는다.