Một ngân hàng có ~n~ chi nhánh, mỗi chi nhánh có một máy chủ, các máy chủ ở các chi nhánh được đánh số từ ~1~ đến ~n~. Nhằm bảo đảm việc truyền thông giữa các chi nhánh, ngân hàng đã thuê ~n - 1~ kênh truyền tin trực tiếp từ một nhà máy cung cấp dịch vụ mạng để kết nối ~n~ máy chủ thành một mạng máy tính và bảo đảm từ máy chủ của một chi nhánh bất kì có thể truyền tin đến tất cả các máy chủ của các chi nhánh còn lại theo kênh truyền tin trực tiếp giữa chúng hoặc thông qua đường truyền đi qua một số máy chủ của các chi nhánh nào đó.

Trong thời gian tới, ngân hàng muốn lựa chọn ~k~ máy chủ trong ~n~ máy chủ để cài đặt phần mềm kiểm soát. Phần mềm khi hoạt động sẽ làm tăng lưu lượng truyền trên các kênh giữa ~k~ máy chủ này. Với mỗi phương án chọn ~k~ máy chủ để cài đặt phần mềm, trong số ~n - 1~ kênh truyền tin, nhà cung cấp dịch vụ mạng đã xác định một số ít nhất các kênh đủ để kết nối ~k~ máy chủ này và khuyến cáo ngân hàng cần phải nâng cấp các kênh đó. Vì lí do kĩ thuật cũng như kinh phí, ngân hàng muốn lựa chọn ~k~ máy chú để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp có giá trị nằm trong đoạn ~[a, b]~. Cụ thể, với một cách chọn ~k~ máy chủ, gọi ~s~ là số kênh ít nhất cần chọn ra trong ~n - 1~ kênh truyền tin nhằm bảo đảm liên thông giữa ~k~ máy chủ được chọn ngay cả khi các kênh còn lại bị đứt kết nối, ~s~ kênh này sẽ được khuyến cáo nâng cấp, khi đó, cách chọn ~k~ máy chủ thỏa mãn yêu cầu của ngân hàng nếu ~a \le s \le b~.

Yêu cầu: Cho ~n - 1~ kênh truyền tin và các giá trị ~k, a, b~, hãy đếm số lượng cách chọn ~k~ máy chủ để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp nằm trong đoạn ~[a, b]~.

Dữ liệu

Vào từ đầu vào chuẩn (không phải file COMNET.INP):

• Dòng thứ nhất chứa bốn số nguyên dương ~n, k, a, b (k < n; 1 < a \le b < n)~;
• Dòng thứ i trong số ~n - 1~ dòng tiếp theo chứa 2 số nguyên dương ~u_i, v_i~ cho biết có kênh truyền tin trực tiếp giữa hai máy chủ ~u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải file COMNET.OUT) một số nguyên duy nhất là số cách chọn ~k~ máy chủ để cài đặt phần mềm thỏa mãn yêu cầu của ngân hàng.

Ràng buộc

• ~20\%~ số test tương ứng với ~20\%~ số điểm của đề bài thỏa mãn: ~n \le 100~ và ~k = 2~;
• ~30\%~ số test khác tương ứng với ~30\%~ số điểm của đề bài thỏa mãn: ~n \le 100~ và ~k = 3~;
• ~20\%~ số test khác tương ứng với ~20\%~ số điểm của đề bài thỏa mãn: ~n \le 100~ và ~k = 4~;
• ~20\%~ số test khác tương ứng với ~20\%~ số điểm của đề bài thỏa mãn: ~n \le 1000~ và ~k = 3~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của đề bài thỏa mãn: ~n \le 1000~ và ~k = 4~;

Ví dụ

Input

6 3 2 3
1 2
2 3
3 4
4 5
3 6

Output

14

Giải thích

Có 5 cách chọn 3 máy chủ trong 6 máy chủ mà số kênh cần nâng cấp bằng 2 là:

1. ~(1, 2, 3)~;
2. ~(2, 3, 4)~;
3. ~(2, 3, 6)~;
4. ~(3, 4, 5)~;
5. ~(3, 4, 6)~;

Có 9 cách chọn 3 máy chủ trong 6 máy chủ mà số kênh cần nâng cấp bằng 3 là:

1. ~(1, 2, 4)~;
2. ~(1, 2, 6)~;
3. ~(1, 3, 4)~;
4. ~(1, 3, 6)~;
5. ~(2, 3, 5)~;
6. ~(2, 4, 5)~;
7. ~(2, 4, 6)~;
8. ~(3, 5, 6)~;
9. ~(4, 5, 6)~;

Như vậy có tất cả 14 cách chọn 3 máy chủ trong 6 máy chủ thỏa mãn yêu cầu của ngân hàng.