No tags yet

No tag edit access

time limit per test: 0.5 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard input

output: standard output

output: standard output

Vasya's younger brother Misha 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 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, for example, 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.

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, for example, 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.

The only line of the input 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).

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 letters from A to Z must be used to represent digits from 10 to 35. The self-replicating numbers can be listed in arbitrary order.

Input

Sample input #1

10 4

Sample input #2

12 6

10 4

Sample input #2

12 6

Output

Sample output #1

1

9376

Sample output #2

2

1B3854

A08369

1

9376

Sample output #2

2

1B3854

A08369

Author: | Nikolay Durov |

Resource: | ACM ICPC 2002-2003 NEERC, Northern Subregion |

Date: | November, 2002 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 15:28:38 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|