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 3
128 32
0 0 Output: 14
792805767

hide comments
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