자기복제 수

미샤는 수를 가지고 노는 것을 좋아한다. 며칠 전 미샤는 $9376^2 = 87909376$이고, 제곱한 값의 마지막 네 자리가 다시 $9376$이라는 사실을 발견했다. 미샤는 이런 수를 자기복제 수라고 부른다.

미샤는 10진법 말고 다른 진법도 알고 있어서 2진법이나 16진법의 자기복제 수도 궁금해한다. 진법의 밑 $b$와 자릿수 $n$이 주어질 때, $b$진법으로 $n$자리인 자기복제 수를 모두 찾는 프로그램을 작성하시오.

수 $x$가 $b$진법 $n$자리 자기복제 수라는 것은 다음 두 조건을 모두 만족한다는 뜻이다.

• 앞에 $0$을 붙이지 않고 $x$를 $b$진법으로 적으면 자릿수가 정확히 $n$이다. $0$은 한 자리 수 0으로 본다.
• $x^2$을 $b$진법으로 적었을 때 마지막 $n$자리가 $x$의 표기와 같다. 즉 $x^2 \equiv x \pmod{b^n}$이다.

첫째 줄에 진법의 밑 $b$와 자릿수 $n$이 공백 하나로 구분되어 주어진다. ($2 \le b \le 36$, $1 \le n \le 2000$)

첫째 줄에 $b$진법 $n$자리 자기복제 수의 개수 $K$를 출력한다. 이어지는 $K$개의 줄에 조건을 만족하는 수를 $b$진법으로 한 줄에 하나씩, 값이 작은 것부터 큰 순서로 출력한다.

$b > 10$이면 $10$부터 $35$까지의 숫자를 대문자 A부터 Z까지로 나타낸다. 조건을 만족하는 수가 하나도 없으면 첫째 줄에 $0$만 출력한다.