긴 퍼즐

1차원 퍼즐이 있다. 퍼즐의 각 조각은 길이, 왼쪽 경계의 종류, 오른쪽 경계의 종류 세 값으로 나타낼 수 있다. 경계의 종류는 곧은 경계, 볼록한 경계, 오목한 경계 중 하나이다. 조각은 뒤집을 수 없으므로 왼쪽 경계와 오른쪽 경계를 바꿀 수 없다. 볼록한 경계는 오목한 경계와 모두 연결할 수 있고, 그 반대도 마찬가지이다. 곧은 경계끼리는 연결할 수 없다.

그림 1: 조각의 예

길이가 $l$인 부분을 만들기 위해 여러 조각(하나일 수도 있다)을 차례로 연결하려고 한다. 부분의 왼쪽 경계와 오른쪽 경계는 곧아야 한다. 집합에 있는 모든 조각을 사용해 원하는 부분을 만들 수 있는 조각 집합의 수를 구하라. 수가 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 계산한다. 서로 다른 연결 방법의 수가 아니라 조각 집합의 수를 구해야 한다.

첫째 줄에 정수 $n$과 $l$이 주어진다. $n$은 조각의 수, $l$은 원하는 부분의 길이이다 ($1 \le n \le 300$, $1 \le l \le 300$).

다음 $n$개의 줄에 조각의 설명이 주어진다. 각 줄에는 $a_i$, $b_i$, $c_i$가 주어지며, 각각 조각의 길이, 왼쪽 경계의 종류, 오른쪽 경계의 종류이다 ($1 \le a_i \le l$; $b_i, c_i \in \{\texttt{"in"}, \texttt{"out"}, \texttt{"none"}\}$). 문자열 "in"은 오목한 경계, "out"은 볼록한 경계, "none"은 곧은 경계를 뜻한다.

집합에 있는 모든 조각을 사용해 원하는 부분을 만들 수 있는 조각 집합의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

첫 번째 예제의 퍼즐 조각은 앞의 그림과 같다.

그림 2: 원하는 부분을 만들 수 있는 조각 집합