Naruto có \(N\) cái túi, túi thứ \(i\) có \(A_i\) đồng tiền. Mỗi lần đi làm nhiệm vụ, Naruto sẽ chọn ra một số túi để 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 túi Naruto chọn, cần chọn sao cho \(S \% 2 = P\) (% là phép lấy phần dư, % trong C++ và mod trong pascal). Hỏi Naruto có bao nhiêu cách chọn các túi?

Input

• Dòng đầu gồm 2 số nguyên \(N\) và \(P\).
• 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\)).

Constants

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

Example

2 0 
1 3 

2