Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Self-Replicating Numbers
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 827Accepted: 257
Case Time Limit: 2000MSSpecial Judge

Description

Vasya's younger brother Misha is fond of playing with numbers. Two days ago he discovered that 93762 = 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 Misha often asks Vasya to help him to find new such numbers. To make the things worse Vasya's brother already knows what the scales of notation are, so he asks Vasya to find, forexample, hexadecimal or binary self-replicating numbers.
Vasya wants to help his brother, 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

The only line of the input contains two numbers b and n separated by a single space, the base b of the scale of notation (2 <= b <= 36) and required length n (1 <= n <= 2000).

Output

The first line of the output 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 characters from A to Z must be used to represent digits from 10 to 35 when b > 10. The self-replicating numbers can be listed in arbitrary order.

Sample Input

12 6

Sample Output

2
1B3854
A08369

Source

Northeastern Europe 2002, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator