CF758F.Geometrical Progression

For given n, l and r find the number of distinct geometrical progression, each of which contains n distinct integers not less than l and not greater than r. In other words, for each progression the following must hold: l ≤ a__i ≤ r and a__i ≠ a__j , where _a_1, _a_2, ..., a__n is the geometrical progression, 1 ≤ i, j ≤ n and i ≠ j.

Geometrical progression is a sequence of numbers _a_1, _a_2, ..., a__n where each term after first is found by multiplying the previous one by a fixed non-zero number d called the common ratio. Note that in our task d may be non-integer. For example in progression 4, 6, 9, common ratio is .

Two progressions _a_1, _a_2, ..., a__n and _b_1, _b_2, ..., b__n are considered different, if there is such i (1 ≤ i ≤ n) that a__i ≠ b__i.

给定 $n$、$l$ 和 $r$，求满足以下条件的互不相同的等比数列的个数：每个等比数列包含 $n$ 个互不相同的整数，且均不小于 $l$、不大于 $r$。换言之，对每个等比数列 $a_1,\,a_2,\,\dots,\,a_n$，需满足：对所有 $1 \le i,\,j \le n$ 且 $i \ne j$，有 $l \le a_i \le r$ 且 $a_i \ne a_j$。

等比数列是指形如 $a_1,\,a_2,\,\dots,\,a_n$ 的数列，其中从第二项起，每一项均由前一项乘以一个固定的非零常数 $d$（称为公比）得到。注意，在本题中 $d$ 可以是非整数。例如，在等比数列 $4,\,6,\,9$ 中，公比为 。

若存在某个下标 $i$（$1 \le i \le n$），使得 $a_i \ne b_i$，则称两个等比数列 $a_1,\,a_2,\,\dots,\,a_n$ 与 $b_1,\,b_2,\,\dots,\,b_n$ 是不同的。

The first and the only line cotains three integers n, l and r (1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107).

第一行且唯一一行包含三个整数 $n$、$l$ 和 $r$（$1 ≤ n ≤ 10^7$，$1 ≤ l ≤ r ≤ 10^7$）。

Print the integer K — is the answer to the problem.

输出整数 K —— 即为本题的答案。

These are possible progressions for the first test of examples:

• 1;
• 2;
• 3;
• 4;
• 5;
• 6;
• 7;
• 8;
• 9;

These are possible progressions for the second test of examples:

• 6, 7;
• 6, 8;
• 6, 9;
• 7, 6;
• 7, 8;
• 7, 9;
• 8, 6;
• 8, 7;
• 8, 9;
• 9, 6;
• 9, 7;
• 9, 8.

These are possible progressions for the third test of examples:

• 1, 2, 4;
• 1, 3, 9;
• 2, 4, 8;
• 4, 2, 1;
• 4, 6, 9;
• 8, 4, 2;
• 9, 3, 1;
• 9, 6, 4.

These are possible progressions for the fourth test of examples:

• 4, 6, 9;
• 9, 6, 4.

以下是第一组样例测试的可能数列：

• 1；
• 2；
• 3；
• 4；
• 5；
• 6；
• 7；
• 8；
• 9；
• 10。

以下是第二组样例测试的可能数列：

• 6, 7；
• 6, 8；
• 6, 9；
• 7, 6；
• 7, 8；
• 7, 9；
• 8, 6；
• 8, 7；
• 8, 9；
• 9, 6；
• 9, 7；
• 9, 8。

以下是第三组样例测试的可能数列：

• 1, 2, 4；
• 1, 3, 9；
• 2, 4, 8；
• 4, 2, 1；
• 4, 6, 9；
• 8, 4, 2；
• 9, 3, 1；
• 9, 6, 4。

以下是第四组样例测试的可能数列：

• 4, 6, 9；
• 9, 6, 4。