Có ~N~ đồ vật, đồ vật thứ ~i~ có trọng lượng ~w_i~ và giá trị ~v_i~. Hãy đếm số tập con (theo vị trí) sao cho tổng trọng lượng đúng bằng ~W~ và tổng giá trị đúng bằng ~V~.

Kết quả lấy modulo ~10^9 + 7~.

Input

• Dòng đầu gồm ba số nguyên ~N~, ~W~, ~V~ (~1 \le N \le 50~, ~1 \le W \le 500~, ~1 \le V \le 500~).
• ~N~ dòng tiếp theo, dòng ~i~ gồm hai số nguyên ~w_i~ và ~v_i~ (~1 \le w_i \le 50~, ~1 \le v_i \le 50~).

Output

In ra số tập con thỏa mãn modulo ~10^9 + 7~.

Ví dụ

Input 1

4 5 6
2 3
3 3
1 2
4 4

Output 1

2

Giải thích 1

• Tập ~\{(2,3), (3,3)\}~: tổng ~w = 5~, tổng ~v = 6~. ✓
• Tập ~\{(1,2), (4,4)\}~: tổng ~w = 5~, tổng ~v = 6~. ✓

Input 2

3 3 3
1 1
1 1
1 1

Output 2

1

Giải thích 2

Chỉ có một cách chọn cả ~3~ đồ vật.

Giới hạn