Bedao Mini Contest 16 - NUMBER

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ở trường mẫu giáo, nkwn đang được dạy về cách ghép những chữ số. Thầy giáo của nkwn muốn giao cho cả lớp bài tập như sau:

Cho một dãy ~A~ gồm ~n~ số tự nhiên từ ~0~ đến ~9~ và một số ~k~. Hỏi có bao nhiêu dãy con của ~A~ gồm ~k~ phần tử, mà các phần tử của dãy con này hợp lại thành 1 số chẵn có nghĩa? Biết một số được gọi là số có nghĩa khi số đó không có chữ số ~0~ đứng đầu nếu số đó là số có nhiều hơn 1 chữ số.

Nhưng bạn nkwn mải chơi nên quên hoàn thành bài tập. nkwn không muốn bị thầy mắng, nên nhờ bạn giúp đỡ bạn ấy hoàn thành nhé!

Dãy con (subsequence) là dãy có thể được suy ra từ dãy đã cho bằng cách xóa một số hoặc không có phần tử nào mà không thay đổi thứ tự của các phần tử còn lại. Ví dụ, dãy ~(1, 2, 5)~ là dãy con của dãy ~(1, 2, 3, 4, 5)~.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~, là độ dài dãy ~A~.
  • Dòng thứ hai chứa ~n~ số tự nhiên ~A_i (0 \le A_i \le 9)~, mỗi số được ngăn cách với nhau bằng một dấu cách.
  • Dòng thứ ba chứa số ~k~ ~(1 \le k \le 30)~ là độ dài của dãy con.

Output

  • In ra một dòng duy nhất chứa số lượng dãy con tạo thành số chẵn có nghĩa modulo ~10^9 + 7~.

Scoring

  • ~40\%~ số test có ~1 \le n \le 20~.
  • ~60\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

5
1 1 0 1 0
3

Sample Output 1

6

Notes

  • Ở test ví dụ, ta có thể thấy có ~6~ dãy con tạo nên số chẵn có nghĩa:

~[1 , 2 , 3] = 110~.

~[1 , 2 , 5] = 110~.

~[1 , 3 , 5] = 100~.

~[1 , 4 , 5] = 110~.

~[2 , 3 , 5] = 100~.

~[2 , 4 , 5] = 110~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.