Suppose you have a multiset of numbers . Suppose is the smallest number and is the largest number in the set. In each move, you can remove and from the set and add instead. So in each step, size of the set decreases by one. After moves are performed, you have only one number remaining in the set. Let's call this number survivor of the set.
The value of a set is defined as the sum of survivors of all non-empty subsets of it.
In this problem, you have an array where and . You have answer queries of this format: given and , what is the value of the set containing ? Since the value can be extremely large, output the answer modulo .
First line contains the value of ().
Second line contains integers. -th integer of this line represents the value of .
Third line contains the value of ().
Next lines contain two integers and , representing the parameters of the query.
Output lines: -th line contains the answer for the -th query.
5 3 4 1 5 6 3 1 5 1 1 3 4
5775 3 11
In the third query, the set is . So the subsets are , and . The survivors are 1, 5 and 5 respectively, which adds up to 11.
The difference between a set and a multiset is that unlike set, multiset can contain same element more than once. For sake of clarity, every mention of a set indigates a multiset in this problem.