{"raw_statement":[{"iden":"statement","content":"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_.\n\nGeometrical 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 .\n\nTwo 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_."},{"iden":"input","content":"The first and the only line cotains three integers _n_, _l_ and _r_ (1 ≤ _n_ ≤ 107, 1 ≤ _l_ ≤ _r_ ≤ 107)."},{"iden":"output","content":"Print the integer _K_ — is the answer to the problem."},{"iden":"examples","content":"Input\n\n1 1 10\n\nOutput\n\n10\n\nInput\n\n2 6 9\n\nOutput\n\n12\n\nInput\n\n3 1 10\n\nOutput\n\n8\n\nInput\n\n3 3 10\n\nOutput\n\n2"},{"iden":"note","content":"These are possible progressions for the first test of examples:\n\n*   1;\n*   2;\n*   3;\n*   4;\n*   5;\n*   6;\n*   7;\n*   8;\n*   9;\n*   10.\n\nThese are possible progressions for the second test of examples:\n\n*   6, 7;\n*   6, 8;\n*   6, 9;\n*   7, 6;\n*   7, 8;\n*   7, 9;\n*   8, 6;\n*   8, 7;\n*   8, 9;\n*   9, 6;\n*   9, 7;\n*   9, 8.\n\nThese are possible progressions for the third test of examples:\n\n*   1, 2, 4;\n*   1, 3, 9;\n*   2, 4, 8;\n*   4, 2, 1;\n*   4, 6, 9;\n*   8, 4, 2;\n*   9, 3, 1;\n*   9, 6, 4.\n\nThese are possible progressions for the fourth test of examples:\n\n*   4, 6, 9;\n*   9, 6, 4."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"给定 #cf_span[n]、#cf_span[l] 和 #cf_span[r]，求满足以下条件的互不相同的几何序列的个数：每个序列包含 #cf_span[n] 个互不相同的整数，且每个数都不小于 #cf_span[l] 且不大于 #cf_span[r]。换句话说，对于每个序列 #cf_span[a1, a2, ..., an]，必须满足 #cf_span[l ≤ ai ≤ r] 且 #cf_span[ai ≠ aj]，其中 #cf_span[1 ≤ i, j ≤ n] 且 #cf_span[i ≠ j]。\\n\\n几何序列是一个数列 #cf_span[a1, a2, ..., an]，其中每一项（除第一项外）都是由前一项乘以一个固定的非零常数 #cf_span[d]（称为公比）得到的。注意，在本题中 #cf_span[d] 可以是非整数。例如，在序列 #cf_span[4, 6, 9] 中，公比为 。\\n\\n两个序列 #cf_span[a1, a2, ..., an] 和 #cf_span[b1, b2, ..., bn] 被认为不同，当且仅当存在某个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]）使得 #cf_span[ai ≠ bi]。\\n\\n输入仅一行，包含三个整数 #cf_span[n]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107]）。\\n\\n请输出整数 #cf_span[K] —— 本题的答案。\\n\\n以下是示例中第一个测试用例的可能序列：\\n\\n以下是示例中第二个测试用例的可能序列：\\n\\n以下是示例中第三个测试用例的可能序列：\\n\\n以下是示例中第四个测试用例的可能序列：\\n\\n\"},{\"iden\":\"input\",\"content\":\"输入仅一行，包含三个整数 #cf_span[n]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107]）。\"},{\"iden\":\"output\",\"content\":\"请输出整数 #cf_span[K] —— 本题的答案。\"},{\"iden\":\"examples\",\"content\":\"输入1 1 10输出10输入2 6 9输出12输入3 1 10输出8输入3 3 10输出2\"},{\"iden\":\"note\",\"content\":\"以下是示例中第一个测试用例的可能序列：   #cf_span[1];  #cf_span[2];  #cf_span[3];  #cf_span[4];  #cf_span[5];  #cf_span[6];  #cf_span[7];  #cf_span[8];  #cf_span[9];  #cf_span[10]。以下是示例中第二个测试用例的可能序列：   #cf_span[6, 7];  #cf_span[6, 8];  #cf_span[6, 9];  #cf_span[7, 6];  #cf_span[7, 8];  #cf_span[7, 9];  #cf_span[8, 6];  #cf_span[8, 7];  #cf_span[8, 9];  #cf_span[9, 6];  #cf_span[9, 7];  #cf_span[9, 8]。以下是示例中第三个测试用例的可能序列：   #cf_span[1, 2, 4];  #cf_span[1, 3, 9];  #cf_span[2, 4, 8];  #cf_span[4, 2, 1];  #cf_span[4, 6, 9];  #cf_span[8, 4, 2];  #cf_span[9, 3, 1];  #cf_span[9, 6, 4]。以下是示例中第四个测试用例的可能序列：   #cf_span[4, 6, 9];  #cf_span[9, 6, 4]。 \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, l, r \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^7 $, $ 1 \\leq l \\leq r \\leq 10^7 $.  \nA geometric progression of length $ n $ is a sequence $ (a_1, a_2, \\dots, a_n) $ such that $ a_i = a_1 \\cdot d^{i-1} $ for some $ a_1 \\in \\mathbb{R} $, $ d \\in \\mathbb{R} \\setminus \\{0\\} $, and all $ a_i $ are distinct.\n\n**Constraints**  \n1. $ a_i \\in [l, r] \\cap \\mathbb{R} $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. $ a_i \\neq a_j $ for all $ i \\neq j $  \n3. $ a_1, d $ such that all $ a_i $ are real numbers in $ [l, r] $\n\n**Objective**  \nCount the number of distinct geometric progressions $ (a_1, a_2, \\dots, a_n) $ satisfying the above, where two progressions are distinct if $ a_i \\neq b_i $ for some $ i $.","simple_statement":null,"has_page_source":false}