Длинный пазл

Сложность: 74%

Вы собираете одномерный пазл. Каждая его деталь характеризуется тремя параметрами: длиной, типом левой границы и типом правой границы. Границы бывают трех типов: плоская, выпуклая и вогнутая. Детали нельзя разворачивать, то есть менять местами левую и правую границы. Любая выпуклая граница стыкуется с любой вогнутой и наоборот. Стыковать детали плоскими границами нельзя.

Примеры деталей

Вы хотите соединить последовательно несколько деталей (возможно, одну), чтобы получился кусок длины ll. Левая и правая границы куска должны быть плоскими. Найдите количество подмножеств деталей, из которых можно собрать требуемый кусок, по модулю 10000000071\,000\,000\,007. Обратите внимание, что вам нужно найти именно количество различных подмножеств деталей, а не количество различных способов, которыми можно детали соединить.

Входные данные

В первой строке даны два целых числа nn и ll – количество деталей пазла и требуемая длина собранного куска (1n3001 \le n \le 300, 1l3001 \le l \le 300).

В следующих nn строках дано описание деталей пазла. Каждая строка содержит aia_i, bib_i и cic_i – длину детали, тип левой границы и тип правой границы, соответственно (1ail1 \le a_i \le l; bi,ci{b_i, c_i \in \{in ,out, none}\}). Строка in соответствует вогнутой границе, out – выпуклой, none – плоской.

Выходные данные

Выведите одно целое число – остаток от деления количества подмножеств деталей, из которых можно собрать требуемый кусок, на 10000000071\,000\,000\,007.

Подзадачи

баллынеобх. подзадачиограничения
1

20

-

n20n \le 20

2

20

-

bi{b_i \in \{in, none}\}, ci{c_i \in \{out, none}\}

3

20

-

n,l50n, l \le 50

4

20

3

n,l100n, l \le 100

5

20

1, 2, 3, 4

Нет дополнительных ограничений

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

Примечание

Детали пазла из первого примера соответствуют иллюстрации выше.

Подмножества деталей, из которых можно собрать кусок требуемой
длины