There is a sequence of N candies in the store. There are different types of candies, the type of the i-th candy is denoted by A_i.

Andy decided to split the sequence into continuous subarrays so that all the following conditions are satisfied

Each candy is contained in exactly one subarray
The size of each subarray is no more than K
For each subarray there is at most one type of candy which is contained an odd number of times

The value of subarray A_L, A_L+1, ..., A_R is defined as A_L+A_R. The value of splitting is defined as the sum of values of the subarrays.

Output the minimum possible value of splitting.

As the answer can be pretty large output it modulo 1000000007 (10⁹+7)

Input format

Output format

An integer denoting the minimum value of splitting modulo 1000000007 (10⁹+7)

Constraints

1 ≤ N ≤50000

1 ≤ K ≤ N

1 ≤ A_i ≤ 5