← 返回题目列表

Codeforces · 121/C

C. 幸运排列

中文机器翻译题面 查看原题

Petya 喜欢幸运数字。大家都知道,幸运数字是正整数,其十进制表示只包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

有一天,Petya 梦想着从 1 到 n 的整数的字典顺序第 k 次排列。确定排列中有多少个幸运数字位于索引也是幸运数字的位置上。

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 109) — 排列中的元素数量和排列的字典序号。

输出

如果从 1 到 n 的第 k 个数字排列不存在,则打印单个数字“-1”(不带引号)。否则,打印问题的答案:这样的索引i的个数,即i和ai都是幸运数字。

示例

输入 #1

7 4

输出 #1

1

输入 #2

4 7

输出 #2

1

注意

排列是 n 个元素的有序集合,其中从 1 到 n 的每个整数恰好出现一次。索引为 i 的位置上的排列元素表示为 ai (1 ≤ i ≤ n)。如果存在 a i (1 ≤ i ≤ n)、ai < bi,并且对于任何 j (1 ≤ j < i) aj = bj,则排列 a 按字典顺序小于排列 b。让我们列出 n 个元素的所有可能排列,并按字典序递增的顺序对其进行排序。那么字典顺序上的第 k 个排列就是这个排列列表的第 k 个元素。

在第一个示例中,排列如下所示:

1 2 3 4 6 7 5

唯一合适的位置是 4。

在第二个示例中,排列如下所示:

2 1 3 4

唯一合适的位置是 4。