Tạo số hợp lệ

Trong một chương trình truyền hình trí tuệ, MC đã đưa ra một thử thách thú vị cho FullHouse Dev. Họ được cung cấp một dãy số và phải tìm ra có bao nhiêu cách để tạo thành các số hợp lệ.

Bài toán

FullHouse Dev nhận được một mảng \(A\) gồm \(n\) số nguyên, mỗi số là một chữ số trong khoảng từ \(0\) đến \(9\). Họ cũng được cho một số nguyên \(k\). Nhiệm vụ của họ là đếm xem có bao nhiêu dãy con của mảng \(A\) tạo thành một số hợp lệ có \(k\) chữ số.

Một dãy con có độ dài \(k\) được gọi là số hợp lệ nếu số đó không có số 0 ở đầu.

Lưu ý:

• Dãy con của một mảng không nhất thiết phải liên tiếp.
• Ví dụ, nếu mảng là \([1, 0, 2]\), thì dãy con \([1, 0]\) không được coi là số hợp lệ có 2 chữ số. Một số hợp lệ có 2 chữ số trong mảng này là \([1, 2]\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - kích thước của mảng.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).
• Dòng thứ ba chứa số nguyên \(k\).

OUTPUT FORMAT:

• In ra số lượng số hợp lệ có \(k\) chữ số có thể tạo được, lấy phần dư khi chia cho \(10^9 + 7\).

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(0 \leq A[i] \leq 9\)
• \(1 \leq k \leq n\)

Ví dụ

INPUT

5
1 1 0 1 0
3

OUTPUT

9

Giải thích

Trong ví dụ trên, các dãy con tạo thành số hợp lệ có 3 chữ số là:

• 111
• 110
• 101
• 101
• 101
• 110
• 111
• 110
• 101

Vì vậy, có tổng cộng 9 cách để tạo số hợp lệ có 3 chữ số từ mảng đã cho.