E. Деревянный забор
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Недавно Вася купил земельный участок и теперь решил огородить его деревянным забором.

Он обратился в компанию «Деревянная доска» по производству деревянных досок для заборов. В каталоге товаров Вася прочитал, что компания имеет в своем распоряжении n различных типов древесины. Из i-го типа древесины компания производит доску, которая представляет собой прямоугольный брусок размером ai на bi.

Вася решил заказать в этой компании доски и построить из них свой забор. Оказалось, что склад компании настолько большой, что Вася может заказать произвольное количество досок каждого из типов. Заметим, что при формировании забора, доски разрешается поворачивать. Однако, поворачивать квадратные доски запрещено.

Васе требуется построить забор длины l, однако произвольный забор ему не подходит. Он хочет, чтобы его забор выглядел красиво. Будем говорить, что забор красивый тогда и только тогда, когда выполняются два условия:

  • не существует двух подряд идущих досок одного типа древесины
  • первая доска забора имеет произвольную длину, а длина каждой последующей доски равна ширине предыдущей

Другими словами, забор считается красивым, если тип древесины i-ой доски забора отличен от типа древесины i - 1 доски, а также длина i-ой доски совпадает с шириной i - 1 доски (для всех i, начиная с 2).

Теперь Васю заинтересовал следующий вопрос — сколькими способами он может подобрать забор для своего участка. От Вас требуется посчитать количество различных красивых заборов длины l.

Два забора будем считать одинаковыми, если соответствующие последовательности типов древесины досок заборов совпадают с учетом их поворотов, в противном случае заборы различны. Поскольку искомое количество может быть достаточно большим, ответ требуется посчитать по модулю 1000000007 (109 + 7).

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

В первой строке заданы два целых числа n и l (1 ≤ n ≤ 100, 1 ≤ l ≤ 3000) — количество различных типов досок и длина забора, соответственно. Далее в n строках следует описание типов досок: i-ая строка содержит два целых числа ai и bi (1 ≤ ai, bi ≤ 100) — размеры доски из i-го типа древесины. Все числа в строках разделены пробелами.

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

Выведите единственное целое число — искомое количество способов по модулю 1000000007 (109 + 7).

Примеры
Входные данные
2 3
1 2
2 3
Выходные данные
2
Входные данные
1 2
2 2
Выходные данные
1
Входные данные
6 6
2 1
3 2
2 5
3 3
5 1
2 1
Выходные данные
20
Примечание

В первом примере существует ровно два способа построить красивый забор длины 3:

  • В качестве первой доски забора использовать доску первого типа с длиной 1 шириной 2. В качестве второй доски использовать доску второго типа с длиной 2 шириной 3.
  • Использовать одну доску второго типа, повернув её. Её длина будет равна 3, а ширина — 2.