Tạo số hợp lệ

Trong một buổi tối đầy sao, FullHouse Dev đang ngồi trong thư viện cổ và tìm thấy một cuốn sách cổ xưa. Khi mở ra, họ phát hiện một bài toán thú vị về cách tạo ra các số kỳ diệu từ một dãy số cho trước.

Bài toán

Cho một mảng \(A\) gồm \(n\) số nguyên. Mỗi số trong mảng là một chữ số đơn trong khoảng từ \(0\) đến \(9\). Bạn cũng được cho một số \(k\). Nhiệm vụ là đếm 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ố được tạo thành 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 cho là \([1, 0]\), thì dãy con \([0]\) không được coi là số hợp lệ 1 chữ số. Một số hợp lệ 1 chữ số trong mảng này là \([1]\).

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.
• Dòng thứ ba chứa số nguyên \(k\).

OUTPUT FORMAT:

• In ra số lượng số hợp lệ \(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 9\)

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ệ 3 chữ số là:

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

Tổng cộng có 9 cách tạo số hợp lệ 3 chữ số từ mảng đã cho.