Lớp của Minh có ~n~ học sinh đứng thành một hàng, đánh số từ ~1~ đến ~n~ theo thứ tự từ đầu hàng. Học sinh thứ ~i~ có mức học lực là số nguyên dương ~a_i~. Một số học sinh trong lớp là cán sự lớp.

Cô giáo chủ nhiệm chia cả hàng thành các nhóm ôn tập. Mỗi nhóm gồm những học sinh đứng liên tiếp nhau trong hàng, và mỗi học sinh thuộc đúng một nhóm. Một nhóm được gọi là hợp lệ nếu thỏa mãn đồng thời hai điều kiện:

• Trong nhóm có không quá ~K~ mức học lực khác nhau, để các bạn trong nhóm còn kèm cặp được nhau.

• Trong nhóm có ít nhất một cán sự lớp, để nhóm có người điều hành.

Một cách chia được gọi là hợp lệ nếu mọi nhóm trong cách chia đó đều hợp lệ. Hai cách chia được coi là khác nhau nếu tồn tại hai học sinh thuộc cùng một nhóm ở cách chia này nhưng thuộc hai nhóm khác nhau ở cách chia kia.

Hãy đếm số cách chia hợp lệ. Do kết quả có thể rất lớn, hãy in ra số dư khi lấy kết quả chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên: hai số nguyên ~n~ và ~K~ ~(1 \le n \le 2 \cdot 10^5;\ 1 \le K \le 10^9)~.

• Dòng thứ hai: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~ là mức học lực của từng học sinh.

• Dòng thứ ba: một xâu gồm ~n~ ký tự "0" hoặc "1"; ký tự thứ ~i~ bằng "1" nếu học sinh thứ ~i~ là cán sự lớp, bằng "0" nếu ngược lại.

Output

In ra một số nguyên là số cách chia hợp lệ, ~\bmod 10^9 + 7~. Nếu không có cách chia hợp lệ nào thì in ra 0.

Scoring

Sample Input 1

5 2
1 2 1 3 3
10101

Sample Output 1

5

Notes

Các cán sự lớp là học sinh ~1~, ~3~ và ~5~. Dưới đây là ~5~ cách chia hợp lệ (dấu ~|~ ngăn cách hai nhóm liền nhau):

• ~1\ 2\ |\ 3\ 4\ 5~

• ~1\ 2\ 3\ |\ 4\ 5~

• ~1\ |\ 2\ 3\ |\ 4\ 5~

• ~1\ 2\ |\ 3\ |\ 4\ 5~

• ~1\ 2\ |\ 3\ 4\ |\ 5~

Cách chia ~1\ |\ 2\ 3\ 4\ 5~ không hợp lệ vì nhóm ~2\ 3\ 4\ 5~ có ba mức học lực khác nhau là ~2, 1, 3~, nhiều hơn ~K = 2~.