CF182E.Wooden Fence

Vasya has recently bought some land and decided to surround it with a wooden fence.

He went to a company called "Wooden board" that produces wooden boards for fences. Vasya read in the catalog of products that the company has at its disposal n different types of wood. The company uses the i-th type of wood to produce a board of this type that is a rectangular a__i by b__i block.

Vasya decided to order boards in this company and build a fence from them. It turned out that the storehouse of the company is so large that Vasya can order arbitrary number of boards of every type. Note that Vasya is allowed to turn the boards as he builds the fence. However, Vasya cannot turn square boards.

Vasya is required to construct a fence of length l, however, an arbitrary fence won't do. Vasya wants his fence to look beautiful. We'll say that a fence is beautiful if and only if the following two conditions are fulfilled:

• there are no two successive boards of the same type
• the first board of the fence has an arbitrary length, and the length of each subsequent board equals the width of the previous one

In other words, the fence is considered beautiful, if the type of the i-th board in the fence is different from the i - 1-th board's type; besides, the i-th board's length is equal to the i - 1-th board's width (for all i, starting from 2).

Now Vasya wonders, how many variants of arranging a fence for his land exist. Your task is to count the number of different beautiful fences of length l.

Two fences will be considered the same if the corresponding sequences of fence boards types and rotations are the same, otherwise the fences are different. Since the sought number can be large enough, you need to calculate the answer modulo 1000000007 (109 + 7).

瓦西娅最近购买了一块土地，决定用木栅栏将其围起来。

他前往一家名为“木板公司”的企业，该公司专门生产用于建造栅栏的木板。瓦西娅在产品目录中了解到，该公司目前拥有 $n$ 种不同类型的木材。该公司使用第 $i$ 种木材来生产一块尺寸为 $a_i \times b_i$ 的矩形木板。

瓦西娅决定向该公司订购木板，并用这些木板搭建栅栏。结果发现，该公司的仓库规模非常庞大，因此瓦西娅可以任意订购每种类型的木板（数量无限制）。注意：在搭建栅栏时，瓦西娅可以将木板任意旋转；但正方形木板（即 $a_i = b_i$ 的木板）不允许旋转。

瓦西娅需要搭建总长度恰好为 $l$ 的栅栏，但并非任意一种栅栏都符合要求。瓦西娅希望他的栅栏看起来美观。我们称一个栅栏是美观的，当且仅当满足以下两个条件：

• 不存在两个相邻的木板属于同一种类型；
• 第一块木板的长度可为任意值，而从第二块开始，每块木板的长度必须等于前一块木板的宽度。

换言之，若记栅栏中第 $i$ 块木板的类型为 $t_i$，其长度与宽度分别为 $\text{len}_i$ 和 $\text{wid}_i$（考虑了可能的旋转），则栅栏美观当且仅当：

• 对所有 $i \ge 2$，有 $t_i \ne t_{i-1}$；
• 对所有 $i \ge 2$，有 $\text{len}_i = \text{wid}_{i-1}$。

现在瓦西娅想知道：有多少种不同的方式可以为其土地搭建这样一座栅栏？你的任务是计算长度恰好为 $l$ 的美观栅栏的方案总数。

若两个栅栏对应的木板类型序列及每块木板的旋转方式完全相同，则视为同一方案；否则视为不同方案。由于答案可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

The first line contains two integers n and l (1 ≤ n ≤ 100, 1 ≤ l ≤ 3000) — the number of different board types and the fence length, correspondingly. Next n lines contain descriptions of board types: the i-th line contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ 100) — the sizes of the board of the i-th type. All numbers on the lines are separated by spaces.

第一行包含两个整数 $n$ 和 $l$（$1 \leq n \leq 100$，$1 \leq l \leq 3000$），分别表示不同木板类型的数量和篱笆的长度。接下来的 $n$ 行描述了各种木板类型：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 100$），表示第 $i$ 种木板的尺寸。每行中的所有数字均以空格分隔。

Print a single integer — the sought number of variants modulo 1000000007 (109 + 7).

输出一个整数——所求的方案数对 1000000007（$10^9 + 7$）取模的结果。

In the first sample there are exactly two variants of arranging a beautiful fence of length 3:

• As the first fence board use the board of the first type of length 1 and width 2. As the second board use board of the second type of length 2 and width 3.
• Use one board of the second type after you turn it. That makes its length equal 3, and width — 2.

在第一个样例中，恰好有两种方式可以搭建长度为 3 的美观栅栏：

• 第一块栅栏板使用第一种类型的木板，其长度为 $1$、宽度为 $2$；第二块木板使用第二种类型的木板，其长度为 $2$、宽度为 $3$。
• 将一块第二种类型的木板旋转后使用，使其长度变为 $3$，宽度变为 $2$。