Hàng rào gỗ

Một công ty sản xuất ván gỗ để làm hàng rào. Có $n$ loại ván; ván loại $i$ là một khối chữ nhật kích thước $a_i\times b_i$ (chiều dài $\times$ chiều rộng). Bạn có thể đặt bao nhiêu ván tùy ý của mỗi loại.

Khi ghép ván vào hàng rào, bạn được phép xoay ván ${90}^{\circ }$ (đổi chỗ chiều dài và chiều rộng cho nhau). Tuy nhiên ván vuông (ván có $a_i=b_i$) thì không được xoay.

Cần dựng một hàng rào có tổng chiều dài đúng bằng $l$ (tổng chiều dài của tất cả các ván trong hàng rào). Một hàng rào được gọi là đẹp nếu thỏa mãn cả hai điều kiện sau:

• Không có hai ván liên tiếp cùng loại.
• Ván đầu tiên có chiều dài tùy ý; với mỗi ván kể từ ván thứ hai, chiều dài của nó bằng chiều rộng của ván liền trước.

Hai hàng rào được coi là khác nhau nếu dãy loại ván hoặc dãy trạng thái xoay của chúng khác nhau.

Hãy đếm số hàng rào đẹp có tổng chiều dài đúng bằng $l$. Vì kết quả có thể rất lớn, in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $l$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ là kích thước ván loại $i$.

Dữ liệu ra

• Một số nguyên duy nhất: số hàng rào đẹp có tổng chiều dài $l$, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$
• $1\le l\le 3000$
• $1\le a_i,b_i\le 100$

Ví dụ