提示: 欢迎访问OurACM平台。
Problem 1808 Self-Replicating Numbers

Accept: 9    Submit: 27
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem 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 can be listed in alphabetical arbitrary order.

Sample Input

2 1 10 4

Sample Output

2 0 1 1 9376

Source

Multi-School Training Contest - WHU Site #3

Submit  Back  Status  Discuss