## UCV2013A - Counting Ids

Little Willy just took a compilers course and is trying to implement his own compiler. First he wants to build a table with all the possible ids that a program could have. He knows that his language supports up to N different characters and any id can be up to L characters long. For example, when N = 2 (lets say characters can be 0 or 1), and L = 3, he could have the following ids: {0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111}.

You have to write a program that can help Willy find out the size of the table. Since the answer can be really big, you must print it modulo 1000000007 (10^9+7).

### Input

The input contains several test cases. Each test case will consist of a single line containing two integers N and L. N is the number of characters that can be part of an id and L is maximum lenght supported by the language (1 <= N <= 65535, 1 <= L <= 10^5).

End of the input is indicated by a test case with N = 0, L = 0 that should not be processed.

### Output

For each test case output a single line containing the number of possible ids modulo 10^9+7.

### Example

```Input:
2 3128 320 0

Output:
14792805767```

hide comments
 < Previous 1 2 3 Next > akshayvenkat: 2016-06-28 09:04:38 handle everything in long long Mohit Rathore: 2016-01-10 17:05:37 Must solve spoj.com/problems/DCEPC11B before solving this. prakash_reddy: 2015-08-30 21:15:22 normal algorithm for pow(a,b)-->TLE effective algorithm for pow(a,b)--->AC :.Mohib.:: 2015-05-02 20:01:20 Simplest classical... :) karan: 2015-02-14 11:50:14 time limit is too flexible.can be done in 0.00 :) Jugal kishor sahu: 2014-12-15 14:19:43 Simple series :) make brute force solution and find series. Vaibhav Gosain: 2014-10-26 19:28:46 sayantannitw: do not submit solutions for same questions with more than one account, disqualify your submissions with one of your accounts... Rahul Jain: 2014-09-29 10:38:29 I used long, got WA. Used long long , got AC,,,why? Amitayush Thakur: 2014-06-17 12:46:00 Weak test cases. Doesn't have a test case where N=1. যোবায়ের: 2014-01-05 20:53:42 Your input file should contain some cases where N = 1. Just saying... Last edit: 2014-01-05 20:54:08

 Added by: Hector Navarro Date: 2013-07-22 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Local UCV 2013. Héctor Navarro