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

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

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

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

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

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

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

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