Alden is playing an RPG: Blades in the Dark. Having not rolled a full success on numerous consecutive rolls, Alden would like to know the odds rolling a full success.

A roll, consisting of \(d\) dice, is a full success if at least one dice lands on the highest value face.

Alden has tested that each dice has the same number of sides, that each dice has exactly one highest value face, and that each dice has an equal chance of landing on each face.

Having a limited memory and a dislike for floating-point numbers, Alden would like you to output the number of possible dice configurations which are a full success modulo \(10^4 + 7\) and the number of possible dice configurations which are not a full success modulo \(10^4 + 7\)

Input Specification

One line comprised of two Space Separated Integers:

The number of dice sides \(s\) \((2 \leq s \leq 10^4 + 7)\)

The number of dice \(d\) \((1 \leq d < 10^6)\)

Output Specification

The number of possible dice configurations which are a full success modulo \(10^4 + 7\) and the number of possible dice configurations which are not a full success modulo \(10^4 + 7\)

Sample Input 1

6 1

Sample Output 1

1 5

Sample Input 2

6 2

Sample Output 2

11 25

Sample Input 3

6 8

Sample Output 3

8095 352