Notepad

Observation 1: the number of valid numbers is trivial

Nick wants all base-$b$ numbers of exactly length $n$ with no leading zeroes.

• First digit: $b-1$ choices.
• Remaining $n-1$ digits: $b$ choices each.

So the total count is

$$T=(b-1)b^{n-1}.$$

Yes, that's it. The problem is not counting. The problem is that $b$ and $n$ are so huge they look like they were generated by a keyboard falling down the stairs.

Observation 2: what does the last page contain?

Each page stores exactly $c$ numbers, and Nick fills pages continuously with no gaps.

Therefore the number of entries on the page containing the last number is:

• $T \bmod c$, if $T \bmod c \neq 0$;
• $c$, if $T \bmod c = 0$.

A compact formula is

$$\text{ans} = ((T-1) \bmod c) + 1.$$

So all we really need is $T \bmod c$.

Observation 3: reduce everything modulo $c$

We want

$$T \bmod c = \bigl((b-1) \bmod c\bigr) \cdot \bigl(b^{n-1} \bmod c\bigr) \bmod c.$$

Since $c \le 10^9$, modulo arithmetic is cheap. The monsters are $b$ and $n$, which are given as decimal strings with up to $10^6$ digits.

Computing $b \bmod c$

Standard decimal scan:

$$\text{cur} \leftarrow (10\cdot \text{cur} + \text{digit}) \bmod c.$$

That gives us $a = b \bmod c$.

Then

$$(b-1) \bmod c = (a-1+c) \bmod c.$$

Observation 4: compute $b^{n-1} \bmod c$ without Euler nonsense

This is the only real trick.

Let

$$a = b \bmod c,$$

and let the exponent $E=n-1$ be given as a decimal string.

Suppose we've processed some prefix of $E$ and its value is $p$. If the next digit is $d$, then the new exponent becomes

$$10p+d.$$

Therefore,

$$a^{10p+d} = (a^p)^{10} \cdot a^d.$$

Modulo $c$ this becomes

$$a^{10p+d} \bmod c = \bigl(a^p \bmod c\bigr)^{10} \cdot \bigl(a^d \bmod c\bigr) \bmod c.$$

So we scan the decimal digits of $E$ from left to right and maintain

$$\text{res} = a^{\text{processed prefix}} \bmod c.$$

Transition for next digit $d$:

$$\text{res} \leftarrow \text{res}^{10} \cdot a^d \bmod c.$$

Precompute $a^0, a^1, \dots, a^9$ once. Then each digit is $O(1)$ work.

This works for any modulus $c$. No coprimality, no Euler's theorem, no Chinese remainder wizardry. Just plain algebra. Sometimes the blunt hammer is the best hammer.

Observation 5: we need $n-1$, not $n$

Since the exponent is $n-1$, we decrement the huge decimal string $n$ by one manually:

• go from right to left,
• borrow through trailing zeroes,
• trim leading zeroes,
• if the result is all zeroes, keep a single "0".

For example:

• $1000 \to 999$
• $1 \to 0$

Algorithm

1. Read $b$ and $n$ as strings, $c$ as integer.
2. Compute $a = b \bmod c$.
3. Compute string $E = n-1$.
4. Compute $$p = a^E \bmod c$$ by scanning digits of $E$ with the recurrence above.
5. Compute $$t = ((a-1+c) \bmod c) \cdot p \bmod c.$$
6. Output:
   • $c$, if $t=0$;
   • otherwise $t$.

Correctness sketch

Let $T=(b-1)b^{n-1}$ be the total number of valid numbers.

• The counting formula is correct because the first digit cannot be zero and all others are arbitrary.
• The last page occupancy depends only on $T \bmod c$, with residue $0$ meaning a full page.
• Since multiplication respects modular arithmetic, $$T \bmod c = ((b-1) \bmod c) \cdot (b^{n-1} \bmod c) \bmod c.$$
• The digit-by-digit exponent method is correct because after appending a decimal digit $d$ to a prefix $p$, the exponent becomes $10p+d$, and $$a^{10p+d}=(a^p)^{10}a^d.$$ So the maintained invariant for res stays true after each processed digit.

That nails the result.

Complexity

Let $|b|$ and $|n|$ be the number of decimal digits of $b$ and $n$.

• Computing $b \bmod c$: $O(|b|)$
• Decrementing $n$: $O(|n|)$
• Computing $a^{n-1} \bmod c$: $O(|n|)$

Total:

$$O(|b|+|n|)$$

with $O(1)$ extra memory besides the input strings.

For inputs of size up to $10^6$ digits, that's exactly the kind of no-nonsense solution you want.