Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3448
Doraemon's Number Game II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Doraemon plays game with Nobita one day.

Doraemon gives a number x with length n in base B, then Doraemon removes one digit from number x, the location of this digit is from s to t (3 ≤ st ≤ n). We call the leftmost digit of x the first digit, the rightmost digit of x the nth digit. After removing one digit, we get a number y in base B. Nobita should answer the number of possible values of x which follows the constraint that there exists a corresponding y after removing a digit so that x is divisible by y.

Nobita also wants Doraemon to solve a similar problem. But Nobita is not good at arithmetic, he can only remove the first digit of x to form a new number y. Then Doraemon should answer the number of possible values of x whose corresponding y is a divisor of x.

Input

Input contains multiple cases (1 ≤ case_num ≤ 2000). Process to the end of file. Each case gives the length of the number n(3 ≤ n ≤ 100), base B(2 ≤ B ≤ 32), start position s and end position t(3 ≤ stn) in a single line separated with a single space.

Output

Output contains two numbers separated by a single space, the first is Doraemon's answer, and the second number is Nobita's answer.

Sample Input

3 10 3 3

Sample Output

90 117

Author: QU, Zhe
Contest: ZOJ Monthly, December 2010
Submit    Status