Trong chương D của bí kíp tán gái, ta sẽ biết đến kĩ thuật chọn quà tặng cho crush một cách chính xác nhất, kĩ thuật đó được biết đến như sau:

Bạn có một dãy $n$ món quà với món quà thứ $i$ là số nguyên dương $a_i$ (đúng vậy, lại là tặng quà bằng dãy số), bạn cần chọn trong $n$ món quà đó $k$ món sao cho số tạo bởi các món quà đó (có thể thay đổi thứ tự) là một số nguyên chia hết cho $4$.

Ví dụ, nếu như các món quà của bạn chọn là $5$, $1$ và $2$ thì khi ghép lại tạo thành $512$ là một số chia hết cho $4$ nhưng nếu bạn chọn các món quà $4$, $1$ thì sẽ tạo thành $41$ không chia hết cho $4$.

Nhiệm vụ của bạn là tính số cách chọn quà chính xác để làm crush của bạn vui và hoàn thành phần D. của giáo án này.

Input

• Dòng đầu tiên gồm 2 số nguyên $n$ và $k$ lần lượt là số lượng món quà và số lượng món quà cần chọn. ($1\leq k\leq n\leq 2000$);
• Dòng tiếp theo gồm $n$ số nguyên dương $a_i$ với $a_i$ là món quà thứ $i$. ($a_i\leq 10^9,\ 1\leq i\leq n$)

Output

• Gồm một dòng duy nhất là số cách chọn quà chính xác chia lấy dư cho $10^9 + 7$ (modulo $10^9 + 7$).

Subtasks

• Subtask 1: Đảm bảo $n\leq 16$. (5 điểm)
• Subtask 2: Đảm bảo $a_i\leq 9$. (10 điểm)
• Subtask 3: Không có ràng buộc gì thêm. (235 điểm)

Example

4 2
1 2 4 6

4