Fish's Counting Game

Fish is a fish who lives in the sea. One day, feeling bored, he decided to play a counting game with the following rules:

1. Determine a base B for counting.
2. Determine an interval of integers \([L, R]\).
3. For each integer \(x\) in \([L,R]\), convert \(x\) to its base-\(B\) representation as a string. Then, list all of its contiguous substrings. For example, if the representation is S of length n, then for every pair \(1 \le i \le j \le n\), the substring \(S[i\ldots j]\) is selected.
4. Interpret each substring as a number in base \(B\) (note that the digits for \(B > 10\) are represented by uppercase letters starting from A). Sum all these values together.

Your task is to verify Fish's result by computing the sum of all the numbers obtained from all the substrings of every number in the interval. There is no modulus.

Note: When converting a number to its base-\(B\) representation, if \(x = 0\) then its representation is "0". For any other \(x > 0\), repeatedly divide \(x\) by \(B\) to form its representation.

In summary, given the base B and the interval limits L and R, compute:

\[ \text{Total} = \sum_{x=L}^{R} \;\sum_{\text{substring }s \text{ of } S_x} \texttt{value}_B(s), \]

where \(S_x\) is the base-\(B\) representation of \(x\), and \(\texttt{value}_B(s)\) denotes the integer value of substring \(s\) read in base \(B\).

inputFormat

The input consists of a single line containing three space-separated integers: B, L, and R, where:

• B (2 ≤ B ≤ 36) is the base for conversion.
• L and R (0 ≤ L ≤ R ≤ 10⁴) define the interval.

outputFormat

Output a single integer, which is the sum of all the values obtained from every contiguous substring of the base-B representation of every number in the interval \([L, R]\).

sample

10 1 9

45