Statement

Stefan has big plans for the year that just begun and among others, one of his plans is to improve his contest ratings. While every competitive programmer dreams of this, he is perfectly aware that not everyone can achieve it. Now he stumbled across an array that he received as a gift many years ago, together with a very old scroll containing the problem statement below. You are given an array V of N positive integers, numbered from 0 to N-1, inclusive. You have to answer Q queries: given L, R and K, find the product of the largest K values of V_L, V_L+1, …, V_R-1, V_R. Stefan realized that this is not a cakewalk question so now it's your turn to help him overcome this challenge and write a program that answers the queries for him. Since the answers can be very big, you have to print them module 10^9 + 7 (i.e. the reminder of the division by 10^9 + 7).