Given a tree with N nodes and k leaves. Some positive values are given to the leaf nodes. There are 2 types of nodes in the tree. The nodes that takes max of all the value of the child nodes and the other nodes that takes min of all the values of child nodes. Given the tree with N nodes, the values that can be given K leaf node and good , bad nodes. What is the maximum possible value that root node can get if arrange k values to k leaf node optimally.

You are given an array A of size N.

Let B denote the list of all N*(N+1)/2 subarray sums of A sorted in non-increasing order.

Your task is to return the Kth element in B. Since the answer can be very large return it modulo 10+7

1<=N<=10**5 1<=K<=min(N*(N+1)/2,10**5) 1<=a[i]<=10**9