This problem statement contains superscripts that may not display properly outside the applet.
Kitayuta Mart is the largest supermarket in Shuseki Kingdom, offering a great variety of food and household products. The main products are fruits, especially apples. The store sells K kinds of apples, numbered from 1 to K. The price system is a little special: the original price of an apple of kind i (1 <= i <= K) is i yen (the currency of the kingdom). However, if a customer wants to buy more than one apple of kind i, the second apple will cost 2*i yen, the third apple will cost 22*i yen, and so on. In general, if a customer is buying n apples of kind i, the actual price of the j-th (1 <= j <= n) apple will be 2j-1*i yen. The store has a sufficient supply of each kind of apples.
Lun the dog loves apples. She wants to buy N apples at Kitayuta Mart. The kinds of apples does not matter to her, thus she will choose N apples so that the total price calculated using the above formula is minimized. You are given two ints: N and K. Find and return the actual price (NOT the original price) of the apple with the highest actual price among the apples that she will buy modulo 1,000,000,007.