CF182E Wooden Fence

Vasya 最近买了一块地，并决定用木栅栏把它围起来。 他去了一家名叫 “Wooden board” 的公司，这家公司生产用于栅栏的木板。Vasya 在产品目录中看到，该公司有 $n$ 种不同类型的木材。该公司会用第 $i$ 种木材生产出尺寸为 $a_{i} \times b_{i}$ 的矩形木板。 Vasya 决定在这家公司订购木板，并用这些木板来建造栅栏。事实证明，这家公司的仓库足够大，Vasya 可以任意数量地订购每种类型的木板。需要注意的是，Vasya 可以在建造栅栏时旋转木板，但**不能旋转正方形木板**。 Vasya 需要建造一个长度为 $l$ 的栅栏，但随便什么栅栏他都不满意。他想要栅栏看起来漂亮。如果满足下列两个条件，我们就认为栅栏是漂亮的： - 不能有连续两块木板类型相同； - 栅栏的第一块木板可以任意选择长度，之后每一块木板的长度等于前一块木板的宽度。 换句话说，如果第 $i$ 块木板的类型和旋转方式与第 $i-1$ 块木板相同，则该方案不漂亮；此外，从第二块木板起，每块木板的长度要等于前一块木板的宽度。 现在 Vasya 想知道，有多少种不同的漂亮栅栏可以围住他的土地，栅栏的总长度要求正好是 $l$。 如果两组栅栏在木板类型和旋转序列上完全一样，则视为相同的栅栏，否则为不同的栅栏。由于答案可能很大，请输出答案对 $1000000007$ ($10^9+7$) 取模后的结果。

第一行包含两个整数 $n$ 和 $l$（$1 \leq n \leq 100,1 \leq l \leq 3000$），表示木板类型数以及栅栏的总长度。 接下来的 $n$ 行，每行包含两个正整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 100$），表示第 $i$ 种木板的尺寸。各行之间数据用空格隔开。

输出一个整数，表示不同漂亮栅栏方案数对 $1000000007$ 取模的结果。

在第一个样例中，恰好存在两种漂亮栅栏长为 $3$ 的方案： - 第一种方案，第一块使用第 $1$ 种类型（长度为 $1$，宽度为 $2$），第二块使用第 $2$ 种类型（长度为 $2$，宽度为 $3$）。 - 第二种方案，第一块使用第 $2$ 种类型，旋转过后（此时长度为 $3$，宽度为 $2$），且不接第二块。 由 ChatGPT 5 翻译