# 4
Cho dãy số nguyên dương $a_1, a_2, \ldots,a_n$. Hãy đếm xem có bao nhiêu cách chọn ra $k$ phần tử từ dãy số trên để các phần tử tạo thành một số nguyên dương chia hết cho 4.

### Input
- Dòng 1 $n\ k$ ($1 \leq k \leq n \leq 2000$)
- Dòng 2 $a_1,a_2,\ldots,a_n$

### Output
- Số cách chọn thoả mãn sau khi modulo cho $10^9+7$

## Solution
Nhắc lại dấu hiệu chia hết cho $4$: Một số chia hết cho $4$ khi và chỉ khi hai chữ số cuối cùng của số đó chia hết cho $4$.

### Trường hợp 1: Tồn tại phần tử nguyên dương $< 10$
- Ta chỉ xét các phần tử $2$, $4$, $6$, $8$;
- Với phần tử $2$, $6$: Chỉ nối được với các phần tử có chữ số cuối cùng là chữ số lẻ (phần tử lẻ)
- Với phần tử $4$, $8$: Chỉ nối được với các phần tử có chữ số cuối cùng là chữ số chẵn (phần tử chẵn) (không tính phần tử đang chọn)
- Sau đó bốc đại ra $k-2$ phần tử còn lại là xong.

### Trường hợp 2: Đối với các phần tử $\geq 10$
- Bốc đại một phần tử chia hết cho $4$, sau đó bốc đại thêm $k-1$ (vì đã bốc trước một số chia hết cho $4$ rồi) phần tử còn lại, rồi hoán vị $k-1$ phần tử đó (vì tính chất của số chia hết cho $4$ nên ta chỉ xét hai chữ số cuối cùng và các chữ số còn lại không ảnh hưởng gì)

### Xây dựng công thức
#### Trường hợp 1
Đối với trường hợp 1: Đối với trường hợp $1$, ta lại chia ra tiếp hai trường hợp con:
- Phần tử bốc được là $2$ hoặc $6$;
- Phần tử bốc được là $4$ hoặc $8$.

Đối với trường hợp phần tử bốc được là $2$ hoặc $6$: Bốc đại thêm một phần tử có đuôi là chữ số lẻ (số lẻ)

Đối với trường hợp phần tử bốc được là $4$ hoặc $8$: Bốc đại thêm một phần tử có đuôi là chữ số chẵn (số chẵn) (không tính phần tử đang chọn)

Sau khi bốc xong, bốc thêm $k-2$ phần tử bất kỳ trong số $n-2$ phần tử còn lại.

Áp dụng công thức cộng và công thức nhân ta có:
$$T_1=\left(C^1_{hs}\times C^1_{od} + C^1_{bt} \times \left(C^1_{ev}-1\right)\right)\times \left[ C^{k-2}_{n-2}\times (k-2)! \right]$$

#### Trường hợp 2
Đối với với trường hợp 2: Đối với các phần tử $\geq 10$, ta chỉ cần bốc đại ra một số $\geq 10$ chia hết cho $4$, sau đó bốc đại ra $k-1$ phần tử trong số $n-1$ phần tử còn lại rồi hoán vị chúng là xong.

Áp dụng công thức cộng và nhân ta có:

$$T_2 = C^1_{x}\times C^{k-1}_{n-1}\times (k-1)!$$

Theo công thức cộng ta có: $$T=T_1+T_2$$

### Hướng dẫn code
- Để dễ hình dung khi code, công thức được tóm lại như sau:

$$T=\left(hs\times od + bt\times (ev-1)\right)\times \dfrac{(n-2)!}{(k-2)!\times (n-k)!}+x\times \dfrac{(n-1)!}{(k-1)!\times (n-k)!}\times(k-1)!$$

trong đó:
- $hs$ là số lượng phần tử $2$ và $6$ trong dãy;
- $od$ là số lượng phần tử lẻ trong dãy;
- $bt$ là số lượng phần tử $4$ và $8$ trong dãy;
- $ev$ là số lượng phần tử chẵn trong dãy;
- $x$ là số lượng phần tử lớn hơn hoặc bằng $10$ và chia hết cho $4$

Áp dụng công thức mod vào nữa là xong.