COIN

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input 
2 0 
1 3
Output 
2
Note
  • Cách 1: Không chọn cái nào.
  • Cách 2: Chọn cả 2 túi. \(1 + 3 = 4, 4\%2 = 0 = P\).

Bình luận