An có \(N\) món quà, món thứ \(i\) có \(A_i\) đồng tiền. Mỗi lần đi làm từ thiện, An sẽ chọn ra một số món để mang theo nếu thỏa mãn điều kiện sau:

Gọi \(S\) là tổng số tiền trong tất cả các món An chọn, cần chọn sao cho \(S \% 2 = M\) (% là phép lấy phần dư, % trong C++ và mod trong pascal). Hỏi An có bao nhiêu cách chọn các món quà?

Input

• Dòng đầu gồm 2 số nguyên \(N\) và \(M\).
• Dòng tiếp theo gồm \(N\) số là \(A_1, A_2, A_3, ...A_N\).

Output

• Gồm một dòng duy nhất chứa số nguyên là kết quả của bài toán. (Kết quả lấy phần dư với \(10^9 + 7\)).

Example

Input

2 0 
1 3

Output

2

Giải thích

• Cách 1: Không chọn cái nào.
• Cách 2: Chọn cả 2 món. \(1 + 3 = 4, 4\%2 = 0 = M\).

Ràng buộc

• \(1 \leq N \leq 50\).
• \(0 \leq M \leq 1\).
• \(1 \leq A_i \leq 100\).