Self-Replicating Numbers

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2840
64-bit integer IO format: %I64d      Java class name: Main

Description

Sherlock is fond of playing with numbers. Two days ago he discovered that 9376^2 = 87909376 - the last four digits constitute 9376 again. He called such numbers self-replicating.

More precisely, an n-digit number is called self-replicating if it is equal to the number formed by the last n digits of its square. Now Sherlock often asks Xay to help him to find new such numbers. To make the things worse, Sherlock already knows what the scales of notation are, so he asks Xay to find, for example, hexadecimal or binary self-replicating numbers.

Xay wants to help Sherlock, but unfortunately he is very busy now: he is seriously preparing and training for the next ACM Regional Contest. So he asked you to write a program that for a given base b and length n will find all n-digit self-replicating numbers in the scale of notation with base b.

Input

there are multiple test cases. one line of each test case contains two integer numbers b and n separated by a single space, the base b of the scale of notation (2 ≤ b ≤ 36) and the required length n (1 ≤ n ≤ 2000).

Output

For eacho test case, the first line contains K - the total number of self-replicating numbers of length n in base b. Next K lines contain one n-digit number in base b each. Uppercase Latin letters from A to Z must be used to represent digits from 10 to 35. The self-replicating numbers should be output int lexicographic order.

Sample Input

2 1
10 4

Sample Output

2
0
1
1
9376

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .