The memory of Rubina’s computer contains two interesting things: an array of integers and a virus. Each midnight the virus becomes active. It takes each array in memory and *replaces* it with a bunch of new arrays: one for each contiguous subarray of the original array.

For example, if today the memory contains a single array `(1,2,1,3)`

, tomorrow it will contain the following arrays: `(1), (2), (1), (3), (1,2), (2,1), (1,3), (1,2,1), (2,1,3), (1,2,1,3)`

.

As another example, if today the memory contains a single array `(7,7)`

, tomorrow it will contain the following arrays: `(7), (7), (7,7)`

, and the day after tomorrow it will contain the following arrays: `(7), (7), (7), (7), (7,7)`

, and so on.

You are given Rubina’s original array A and the number of days D. Let f(A,D) be the sum of all elements of all arrays that will be in the memory of Rubina’s computer after D days. Our goal is to calculate f(A,D). You may assume that the memory of Rubina’s computer is sufficiently large to accommodate all the arrays.

For example, if A is the array `(1,2,1,3)`

and D = 0 then the answer is `7`

.

If A = `(1,2,1,3)`

and D = 1, what is f(A,D)?

If A = `(500)`

and D = 120, what is f(A,D)?

If A = `(1,2)`

and D = 10, what is f(A,D)?

If A has four elements, how many arrays of length *one* are there after two steps?