Problem Statement

Maximum Position-Weighted Sum of K Items You are given an array a of N positive integers. The array is indexed from 1 to N , and the weight of the element at index i is a[i] × i . Select exactly K elements such that no two selected indices have the same remainder when divided by K . Print the maximum possible sum of the selected weights modulo 1,000,000,007 . Input Format The first line contains N , the size of the array. The second line contains K , the exact number of elements to select and the modulus used for index classes. The third line contains N space-separated integers a[1], a[2], ..., a[N] . Output Format Print one integer: the maximum possible total weight modulo 1,000,000,007 . Constraints 1 ≤ N ≤ 100,000 1 ≤ K ≤ N 1 ≤ a[i] ≤ 10,000 Use 64-bit arithmetic for weights and their sum before taking the modulus. Examples Example 1 Input: 5 3 2 1 4 3 2 Output: 34 Explanation: The best weights in residue classes 1 , 2 , and 0 are 12 , 10 , and 12 , for a total of 34 . Example 2 Inp