Hôm nay, trong lúc tham quan thư viện thành phố, FireGhost130104 bỗng tìm thấy cuốn sách "300 bài code thiếu nhi" nằm gọn một góc, không ai chú ý tới. Anh ấy hiếu kì, lật ra xem ngay bài đầu tiên:

Cho dãy số nguyên ~a~ và dãy nhị phân ~b~ gồm ~n~ phần tử. Cho một hoán vị ~p~ độ dài ~n~, ta sẽ xây dựng dãy ~c~ như sau:

• Đặt ~v_i = b_{p_1} \oplus b_{p_2} \oplus \ldots \oplus b_{p_i}~.

• Nếu ~v_i = 1~, ~c_i = a_{p_i}~; ngược lại, ~c_i = -a_{p_i}~.

Hãy in ra mảng ~c~ sau khi thực hiện các thao tác trên.

"Chậc, bài gì mà dễ thế nhỉ" – FireGhost130104 thầm nghĩ. Với sở thích tăng độ khó cho mọi thứ, chỉ một lúc sau, anh ấy đã nghĩ ra phiên bản khó hơn:

Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử, hãy đếm số hoán vị ~p~ thỏa mãn: ~\sum_{i = 1}^{n} c_i \vdots k~.

Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo ~10^9 + 7~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ (~1 \le n \le 500~) và ~k~ (~1 \le k \le 500~).

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 10^9~).

Dòng thứ ba gồm ~n~ số nguyên ~b_1, b_2, ..., b_n~ (~0 \le b_i \le 1~).

Output

In ra số hoán vị thỏa mãn đề bài theo modulo ~10^9 + 7~.

Scoring

• ~10\%~ số test thoả mãn ~n \le 10~.

• ~90\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4 9
2 5 5 1
1 0 1 0

Sample Output 1

8