<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

159. Self-Replicating Numbers
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard input
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.

Input
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).

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 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.

Sample test(s)

Input
Sample input #1
10 4

Sample input #2
12 6

Output
Sample output #1
1
9376

Sample output #2
2
1B3854
A08369

Note
Author:	Nikolay Durov
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002

<|response|>
1. Abridged problem statement
-----------------------------

We work in base `b` (2 ≤ b ≤ 36). Digits are `0..9,A..Z` = `0..35`.  
An `n`‑digit number `X` (most significant digit non‑zero, except possibly when `n = 1`) is called **self‑replicating** if the last `n` digits of `X²` in base `b` equal `X` itself.

Equivalently, if `bⁿ` is the base power, then:

- `0 ≤ X < bⁿ`,
- the most significant digit of `X` is non‑zero,
- and `X² ≡ X (mod bⁿ)`.

Input: integers `b, n`.  
Output: all `n`‑digit self‑replicating numbers in base `b` in any order, and first output their count. Use uppercase `A..Z` as digits for 10..35.


2. Key observations
-------------------

1. **Algebraic form**  
   Let

   \[
   X = \sum_{i=0}^{n-1} x_i b^i,\quad 0 \le x_i < b,\ x_{n-1}\ne 0\ (n>1).
   \]

   Self‑replicating means

   \[
   X^2 \equiv X \pmod{b^n}.
   \]

2. **Digitwise comparison via multiplication with carries**  
   When you square `X` in base `b`, each term `x_i x_j` contributes to digit position `i + j`.  
   For `i ≠ j`, there are two equal terms (`i,j` and `j,i`), so contribution is `2 x_i x_j`.  
   For `i = j`, contribution is `x_i²`.

   After adding all contributions, we normalize via base `b` (like usual “carry propagation”): a digit is `sum % b`, and we pass `sum / b` to the next position.  
   We need that, after normalization, the digit at each position `k` equals `x_k`.

3. **Incremental construction of digits**  
   We can build `X` digit‑by‑digit from least significant to most:

   - Suppose we have chosen digits `x[0..pos-1]`.
   - We maintain an array `carry[0..n-1]` of current raw coefficients for `X²` up to `b^{n-1}`, already normalized up to position `< pos` so that:
     - For every `k < pos`, `carry[k]` is exactly the final digit of `X²` at position `k`, and it equals `x_k`.

   Then we try all possibilities for the next digit `x[pos]`, update the carries, and check consistency.

4. **Crucial local condition for pruning**  
   When we choose a new digit `x[pos]`, which new terms can affect **position `pos` itself** before normalization?

   - From existing digits `x[0..pos-1]`, we already accounted their pairwise contributions in `carry[pos]`.
   - New digit `x[pos]` will form products with all digits, but:
     - For `j > 0`, `x[pos] x[j]` contributes to position `pos + j > pos` (does not affect digit at `pos`).
     - Only the product with `x[0]` affects position `pos`:
       - If `pos = 0`: term `(0,0)` → coefficient `x₀²`, factor 1.
       - If `pos > 0`: pairs `(pos,0)` and `(0,pos)` → `2 x₀ x_pos`, factor 2.

   So the digit at position `pos`, **before full carry propagation to higher positions**, is:

   \[
   \text{tmp} = carry[pos] + (1 + [pos \ne 0]) \cdot x_0 \cdot x_{pos}
   \]

   Its digit modulo `b` must equal `x_{pos}`; otherwise no later digits can fix it:

   \[
   (\text{tmp} \bmod b) = x_{pos}
   \]

   This is a very strong constraint and dramatically prunes the search space.

   For `pos > 0` it can be written as:

   \[
   (carry[pos] + 2 x_0 x_{pos}) \equiv x_{pos} \pmod{b}
   \quad\Rightarrow\quad
   carry[pos] \equiv (1 - 2 x_0) x_{pos} \pmod{b}.
   \]

   Thus, once `x[0]` is fixed, each further `x[pos]` is essentially determined (0 or 1 choices) for a given `carry[pos]`.

5. **Complexity intuition**

   - We branch over digits for `x[0]` (`0..b-1`, with the eventual leading‑zero restriction at the last position).
   - After that, each next digit is almost fixed by the modular condition.  
   - Depth of recursion is `n ≤ 2000`.
   - Each step does `O(pos)` small integer operations (`≤ 36²` per product).  
   This is efficient enough for the limits.


3. Full solution approach
-------------------------

1. **Representation**

   Store digits `x` in little‑endian: `x[0]` is least significant, `x[n-1]` most significant.  
   Keep an array `carry[0..n-1]` of integers (not reduced modulo `b` until we propagate), representing raw coefficients for powers of `b` in `X²` modulo `bⁿ`.

2. **`pop_carry` function**

   Given an index `pos`, normalize carries starting from `pos`:

   - While `pos < n` and `carry[pos] ≥ b`:
     - Let `full = carry[pos] / b`, `carry[pos] %= b`.
     - If `pos+1 < n`, add `full` to `carry[pos+1]`.
     - Increase `pos` and continue.

   Any carry that would go beyond position `n-1` can be ignored because we work modulo `bⁿ`.

3. **Recursive function `rec(pos)`**

   Parameters (conceptually):

   - `pos`: next digit index to choose (`0..n`).
   - `x`: digits chosen so far (`x[0..pos-1]`).
   - `carry`: current coefficients for `X²`, normalized at all positions `< pos` so that `carry[k] == x[k]` for all `k < pos`.

   Steps:

   - **Base case**: if `pos == n`:
     - All digits picked and conditions satisfied. Convert `x` to output string:
       - Traverse `x` from `x[n-1]` to `x[0]`.
       - Map `0..9` to `'0'..'9'`, `10..35` to `'A'..'Z'`.
       - Save this string as one answer.
     - Return.

   - **Backtracking setup**:
     - Copy current `carry` to `carry_save` to restore after each trial digit.

   - **Digit range**:
     - For the most significant position `pos == n-1` and `n != 1`, digit cannot be `0` (otherwise number would have fewer than `n` digits).
     - So:
       - If `pos == n-1` and `n != 1`: `d` goes from `1` to `b-1`.
       - Otherwise: `d` goes from `0` to `b-1`.

   - For each candidate digit `d`:
     1. Append `d` to `x` as `x[pos]`.

     2. **Quick modular check at position `pos`**  
        Factor is `1` if `pos == 0`, else `2`. Let:

        \[
        \text{tmp} = carry[pos] + \text{factor} \cdot x[0] \cdot x[pos]
        \]

        If `(tmp mod b) != x[pos]`, this digit cannot lead to a valid self‑replicating number:
        - Remove `x[pos]` and try next `d`.

     3. **Add all contributions of the new digit to `carry`**:

        For `j` from `0` to `pos`:

        - factor = `1` if `j == pos` (square term), else `2`.
        - `val = factor * x[pos] * x[j]`.
        - Target index: `idx = pos + j`.
        - If `idx < n`:  
          - `carry[idx] += val`.
          - call `pop_carry(idx)` to normalize from there upward.

        This accounts for all `(pos,j)` and `(j,pos)` terms in `X²`.

     4. **Exact equality check at position `pos`**  
        After adding contributions and propagating carries, the final digit at position `pos` in `X²` is now `carry[pos]` (normalized). It must equal `x[pos]`. If not, branch is invalid.

        If `carry[pos] == x[pos]`:
        - Recurse: `rec(pos + 1)`.

     5. **Backtrack**:
        - Restore `carry` from `carry_save`.
        - Pop `x[pos]`.

4. **Initialization and output**

   - Read `b, n`.
   - Initialize `carry` as an array of size `n` filled with `0`, `x` as empty vector, `ans` as empty list.
   - Call `rec(0)`.
   - Print:
     - Number of answers, `ans.size()`.
     - Then each answer on its own line (any order is allowed).

This fully implements the mathematical condition `X² ≡ X (mod bⁿ)` with backtracking over digits and strong local pruning, and is efficient enough for the given constraints.


4. C++ implementation
--------------------------------------------

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int b, n;

void read() { cin >> b >> n; }

void pop_carry(int pos, vector<int>& carry) {
    if(pos >= n || carry[pos] < b) {
        return;
    }

    int full = carry[pos] / b;
    carry[pos] %= b;
    if(pos + 1 < n) {
        carry[pos + 1] += full;
        pop_carry(pos + 1, carry);
    }
}

void rec(int pos, vector<int>& carry, vector<int>& x, vector<string>& ans) {
    if(pos == n) {
        string candidate = "";
        for(int i = n - 1; i >= 0; i--) {
            if(x[i] >= 10) {
                candidate.push_back(x[i] - 10 + 'A');
            } else {
                candidate.push_back(x[i] + '0');
            }
        }
        ans.push_back(candidate);
        return;
    }

    vector<int> carry_save = carry;
    for(int d = (pos == n - 1) && (n != 1); d < b; d++) {
        x.push_back(d);
        if((carry[pos] + (1 + (pos != 0)) * x[0] * x[pos]) % b != x[pos]) {
            x.pop_back();
            continue;
        }

        for(int j = 0; j <= pos; j++) {
            int val = (1 + (pos != j)) * x[pos] * x[j];
            if(pos + j < n) {
                carry[j + pos] += val;
            }
            pop_carry(pos + j, carry);
        }

        if(carry[pos] == x[pos]) {
            rec(pos + 1, carry, x, ans);
        }

        carry = carry_save;
        x.pop_back();
    }
}

void solve() {
    // The first thing we should notice is that the solution wants us to
    // output all self-replicating numbers. This should immediately suggest
    // looking at brute force solutions. In particular, the number of such
    // numbers is likely not very high. Let us start with considering how
    // a self-replicating number would. Let X = SUM x[i] * b^i. Then we have:
    //
    //     X^2 = X   (mod b^n)
    //     (SUM x[i] * b^i) * (SUM x[i] * b^i) = X   (mod b^n)
    //     SUM x[i] * x[j] * b^(i + j) = X   (mod b^n)
    //
    // In particular, we can notice that all terms with i+j >= n get ignored
    // because of mod b^n. Furthermore, if we start building X from i = 0, we
    // can notice that we can incrementally add the contribution with the
    // previous digits. Lets do a brute force starting from i = 0 and going,
    // where we will keep carry[k] for each b^k. We will try every possible
    // value for x[i], but we know that for i > 0 it should satisfy that:
    //
    //     (carry[i] + 2 * x[i] * x[0]) = x[i]   (mod b)
    //     carry[i] = (1 - 2 * x[0]) * x[i]   (mod b)
    //
    // Most importantly, this means that there are either 0 or 1 solutions after
    // i = 0. The constraint is b <= 36, so we don't have to be careful about
    // quickly finding x[i], but this makes the brute force viable - after
    // choosing x[0] the number is determined (if it's possible).

    vector<int> carry(n, 0), x;
    vector<string> ans;
    rec(0, carry, x, ans);

    cout << ans.size() << endl;
    for(int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
-----------------------------------------------

```python
import sys
sys.setrecursionlimit(10000)  # Ensure recursion depth is safe for n <= 2000


def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    b = int(data[0])  # base
    n = int(data[1])  # length

    # carry[k] stores the raw coefficient for b^k in X^2 (may be >= b before normalization)
    carry = [0] * n

    # x will store digits of X in little-endian order: x[0] is least significant
    x = []

    # List of answer strings
    ans = []

    # Propagate carries starting from index 'pos' upwards
    def pop_carry(pos: int) -> None:
        # While inside the array and we have overflow at carry[pos]
        while pos < n and carry[pos] >= b:
            full = carry[pos] // b   # how many base-b units to carry up
            carry[pos] %= b          # keep remainder as the digit here

            pos += 1
            if pos < n:
                carry[pos] += full   # add carried amount to next position

    def rec(pos: int) -> None:
        # Base case: all digits chosen
        if pos == n:
            # Convert X from little-endian digits to a base-b string
            # with 0..9 and A..Z for digits 10..35.
            chars = []
            for d in reversed(x):
                if d < 10:
                    chars.append(chr(ord('0') + d))
                else:
                    chars.append(chr(ord('A') + d - 10))
            ans.append(''.join(chars))
            return

        # Save current carry state so we can backtrack exactly
        carry_save = carry[:]  # shallow copy of the list

        # Determine starting digit: the most significant digit of an n-digit
        # number (n > 1) cannot be zero.
        if pos == n - 1 and n != 1:
            start_digit = 1
        else:
            start_digit = 0

        for d in range(start_digit, b):
            x.append(d)  # choose digit d at position pos

            # Quick modular feasibility check focusing on index 0 contribution.
            # For position pos, the new contributions to its digit come only
            # from the pair(s) involving x[0]:
            #   pos == 0 -> (0,0) => factor = 1
            #   pos > 0  -> (pos,0) and (0,pos) => factor = 2
            if pos == 0:
                factor = 1
            else:
                factor = 2

            # x[0] is always defined since pos >= 0 (and we just appended x[0] when pos==0).
            tmp = carry[pos] + factor * x[0] * x[pos]

            # The resulting digit at 'pos' modulo b must match x[pos].
            if tmp % b != x[pos]:
                x.pop()  # revert digit
                continue  # try the next digit candidate

            # Now add full contributions from new digit x[pos] with all digits x[j], j=0..pos
            for j in range(pos + 1):
                if j == pos:
                    pair_factor = 1  # square term x[pos]^2
                else:
                    pair_factor = 2  # symmetric pair x[pos]*x[j] + x[j]*x[pos]

                val = pair_factor * x[pos] * x[j]
                idx = pos + j

                if idx < n:
                    carry[idx] += val
                    # normalize from this position
                    pop_carry(idx)
                # if idx >= n, contribution is beyond b^n and is ignored

            # After adding and normalizing, the digit at position pos (carry[pos])
            # must exactly equal the chosen digit x[pos].
            if carry[pos] == x[pos]:
                rec(pos + 1)

            # Backtrack: restore carry and remove last digit
            for i in range(n):
                carry[i] = carry_save[i]
            x.pop()

    # Start recursion from the least significant digit
    rec(0)

    # Output: first the count, then each number on its own line
    out_lines = [str(len(ans))]
    out_lines.extend(ans)
    sys.stdout.write("\n".join(out_lines))


if __name__ == "__main__":
    solve()
```

This Python solution follows exactly the same logic as the C++ one: incremental digit construction, carry maintenance, a strong local constraint to prune impossible branches, and final output in the required base‑`b` representation.