Splitting Candies
Problem
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 Ai.
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 AL, AL+1, ..., AR is defined as AL+AR. 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 (109+7)
Input format
- The first line contains N denoting the number of candies
- The second line contains an integer K denoting the maximum size of a subarray.
- Each of the next N lines contains one integer, the type of each candy.
Output format
An integer denoting the minimum value of splitting modulo 1000000007 (109+7)
Constraints
1 ≤ N ≤50000
1 ≤ K ≤ N
1 ≤ Ai ≤ 5
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
K = 3 A = [1, 1, 3, 1, 3] The optimal splitting will be [1, 1][3, 1, 3] with (A1+A2)+(A3+A5) = 1 + 1 + 3 + 3 = 8 as the value of splitting
