Tìm tất cả các giá trị nguyên dương ~x\ (0< x < 10^9)~ là nghiệm phương trình ~x=b×S(x)^a+c~ trong đó ~a,b,c~ là hằng số cho trước và hàm ~S(x)~ là tổng các chữ số của ~x~.

Input

• Gồm một dòng ghi ba số nguyên ~a,b,c\ (1≤a≤5;1≤b≤10000; |c|≤10000)~.

Output

• Ghi ra một số nguyên duy nhất là số lượng nghiệm nguyên dương ~x~ thỏa mãn phương trình.

Sample

Input #1

3 2 8

Output #1

3

Input #2

1 2 -18

Output #2

0

Hint

Trong #1, các nghiệm là: ~10, 2008, 13726~.

Problem source: Chuyên Sơn La Online Judge