Cắt và Tích

Trong một ngày mưa gió, FullHouse Dev đang ngồi trong văn phòng ấm áp và được giao một bài toán thú vị về mảng số. Họ cần tìm cách cắt một mảng thành các phần và tính toán tổng của tích các phần đó.

Bài toán

Cho một mảng \(A\) gồm \(n\) phần tử. Bạn cần thực hiện đúng \(k\) lần cắt trên mảng để chia mảng thành \(k+1\) mảng con không rỗng. Sau khi mảng được chia thành các phần, bạn cần tính tích các phần tử trong mỗi phần và lấy tổng của tất cả các tích này. Vì có nhiều cách để phân chia mảng thành \(k+1\) mảng con, bạn cần in ra tổng của tất cả các cách có thể theo modulo \(10^9+7\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - số lượng phần tử trong 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\) - số lần cắt cần thực hiện.

OUTPUT FORMAT:

• In ra một số nguyên duy nhất là tổng của tích các mảng con theo tất cả các cách cắt có thể, lấy modulo \(10^9+7\).

Ràng buộc:

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

Ví dụ

INPUT

4
1 2 3 4
2

OUTPUT

35

Giải thích

Có 3 cách để thực hiện 2 lần cắt trong mảng đã cho:

1. 1 | 2 | 3 4

   • Tổng tích: 1 + 2 + (3 × 4) = 15

2. 1 | 2 3 | 4

   • Tổng tích: 1 + (2 × 3) + 4 = 11

3. 1 2 | 3 | 4

   • Tổng tích: (1 × 2) + 3 + 4 = 9

Tổng cuối cùng: 15 + 11 + 9 = 35