Tôi gặp lại Minh, cậu em 96 học Bách Khoa bỏ sang IT mà anh em VOZer hay truyền miệng. Tuy mới 26, nhưng trông Minh còn già cả, tàn tạ hơn cả tôi. Hỏi ra thì mới biết Minh đã bán căn biệt thự, đang ở trọ thuê, hai chị em làm ngân hàng cũng đã đi lấy chồng khác.

Minh ngậm ngùi:

- Cái ngành này tính ra nó bạc anh ạ. Thời Covid, do làm việc tại nhà rảnh quá, nên em kiếm cày thêm cả dự án ngoài. Mệt quá, em đành viện tới cà phê, bò húc để code. Ngày nào cũng uống vài lon, tới lúc đi khám sức khoẻ thì lòi ra tẻo đường nhẹ, trĩ nội trị ngoại đủ cả, lại còn thoát vị đĩa đệm. Tiền bạc trong nhà đội nón ra đi để chữa bệnh.

Tôi tò mò: "Ơ thế đợt trước nghe nói chú đầu tư trúng coin lắm mà?"

Minh đáp: "Em ôm Bitcoin lúc 60k, đến lúc nó còn 30k chưa kịp về bờ thì phải bán đi mua thuốc. Bí quá em nghe thằng Loli gì đấy đầu tư, theo coin nào sập coin đấy."

Tôi chỉ biết thở dài ngao ngán. Cũng may, Minh bảo tôi: "Giờ em bỏ IT, quay lại làm cơ khí. Lương ba cọc ba đồng mà được cái bao ăn, công việc nhẹ nhàng, lại nhẹ đầu anh ạ."

Kết thúc câu chuyện, tôi bước ra, định tính tiền thì nghe Minh gọi vọng lại: "Anh ơi, thanh toán luôn phần em với, tháng này công ty em lại chậm lương rồi!" Chán dã man! Thế là tôi lại phải ra ATM rút thêm ~S~ đồng để trả tiền.

Trong cây ATM có ~n~ loại tiền, loại thứ ~i~ có số lượng ~a_i~ (tờ) và giá trị ~b_i~ (đồng). Số như nào mà tôi lại trúng con ATM muốn số lượng (tờ) của từng loại tiền rút ra là như nhau. Bạn hãy giúp tôi đếm có bao nhiêu cách trả tiền thỏa mãn với! Hai cách được coi là khác nhau nếu tồn tại một loại tiền được rút với số lượng tờ khác nhau trong hai cách đó.

Input:

• Dòng đầu tiên chứa hai số nguyên dương ~N,S\ (N,S \le 6000)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i,b_i~ ~(a_i,b_i \le 6000)~.

Output:

• Một số nguyên là kết quả bài toán, sau khi chia dư cho ~10^9 + 7~. Nếu không có cách nào, in ra ~-1~.

Sample Input 1

6 12
1 12
2 6
3 4
4 3
6 2
12 1

Sample Output 1

12

Sample Input 2

5 20
20 1
10 2
10 3
10 4
10 5

Sample Output 2

10

Ràng buộc

• 40% số test có ~N \le 15,\ S \le 500~.
• 20% số test có ~N \le 200,\ S \le 1000~.
• 15% số test có ~N \le 1500,\ S \le 2000~.
• 25% số test không có ràng buộc gì thêm.