It is said that the Martian are going to have a competition with us.
They give us N kinds of different characters(not just letters), and a number K, we have an expression f which is equal as (c1+c2+c3+……+cn)^k. [ci is one of the giving characters].
Now, what they want to know is number of different terms after f is expanded; do help the earth.

There are muliply test cases;
for each test case,
there is only a line contains the two natural numbers N and K separated by blanks. As you can observe, N and K are both at least 1.

For each test case there is a line contains an answer.
You may safely assume that each answer fits into a 64-bit unsigned integer.