Mirror Split Sum in Base K

lxhgww loves number games. He discovered that many numbers can be represented as the sum of two numbers which are mirror images (digit reversal) of each other, a phenomenon he calls "mirror split". For a given base \(K\), consider a number \(n\) in the interval \([A,B]\). A mirror split of \(n\) is an ordered pair of positive integers \((x,y)\) such that:

• The base-\(K\) representation of \(x\) and \(y\) does not have any leading zeros. In particular, even though a single digit might be 0, a multi-digit number cannot start with 0.
• \(y\) is the reversal of the base-\(K\) representation of \(x\). That is, if \(x\) in base \(K\) is written as \(d_1d_2\ldots d_m\), then \(y\) equals \(d_md_{m-1}\ldots d_1\) (also interpreted in base \(K\)).
• They sum to \(n\): \(x+y=n\).

For example, in base 10, the number \(66\) has five mirror split representations:

\[ 66 = 15+51 = 24+42 = 33+33 = 42+24 = 51+15 \]

Note that an expression like \(66=60+06\) is not valid because \(06\) has a leading zero.

Your task is: Given \(K\) and an interval \([A,B]\), count the total number of ordered pairs \((x,y)\) with the property that \(y\) is the mirror (digit-reversal) of \(x\), neither \(x\) nor \(y\) has leading zeros in their base-\(K\) representations, and \(x+y\) falls within \([A,B]\). Note that if \(x\) and its reverse are distinct, they will contribute as two different ordered pairs (one from \(x\) and one when roles are swapped), whereas a palindromic \(x\) will contribute once.

inputFormat

The input consists of a single line with three integers \(K\), \(A\), and \(B\) separated by spaces, where \(K\) (\(K \ge 2\)) is the base and \(A \le B\) defines the interval \([A,B]\).

outputFormat

Output a single integer: the total count of mirror split representations for all numbers \(n\) such that \(n=x+y\) is in the interval \([A,B]\).

sample

10 66 66

5