Cho xâu nhị phân ~s~ độ dài ~n~. Bạn được thực hiện các thao tác sau bao nhiêu lần tùy ý:

• Xóa ~x~ số 0 kề nhau.
• Xóa ~y~ số 1 kề nhau.
• Đổi vị trí ~2~ số 0 và 1 liền kề.

Đếm xem sau một số hữu hạn các thao tác (có thể không thực hiện bất cứ thao tác nào), có bao nhiêu xâu nhị phân độ dài ~m~ khác nhau có thể được tạo ra. Hai xâu nhị phân khác nhau khi chúng có một vị trí mà ở xâu này là 0 nhưng xâu còn lại là 1.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n, m, x, y~ (~1 \le m \le n \le 2 \times 10^5; 0 \le x, y \le n~).
• Dòng thứ hai chứa xâu nhị phân ~s~.

Output

In ra một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho ~10^9 + 7~.

Scoring

• Subtask 1 (25% số điểm): ~n = m~.
• Subtask 2 (25% số điểm): ~n \le 20~.
• Subtask 3 (25% số điểm): ~n \le 2000~.
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

5 3 1 2
00011

Output

4