Even-Hating Number

Time limit1sMemory limit1024 MB

Summary

Count and find the K-th largest number under 10^N whose digit string uses only 3, 5, 7 and each of these digit counts is odd.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Dodo's friend hates even numbers. So much that just seeing an even number makes him breathe fire and explode with rage.

For his friend, Dodo invented the even-hating number.

An even-hating number consists of $3$ , $5$ , and $7$ , and the count of $3$ s, the count of $5$ s, and the count of $7$ s are simultaneously not even. If a digit is used $0$ times, it is considered even.

For example, $75$ is an even-hating number because the count of $7$ s is $1$ , the count of $5$ s is $1$ , and the count of $3$ s is $0$ , so all digit counts are simultaneously not even.

Write a program that prints the $K$ -th largest even-hating number among numbers less than $10^N$ .

No input is given for which the answer does not exist.

Input

The first line gives the integer $N$ ( $1 \le N \le 30$ ) and the integer $K$ ( $1 \le K \le 2^{63}-1$ ).

Output

On the first line, print the $K$ -th largest even-hating number among numbers less than $10^N$ .

Hint

$2^{63}-1$ can be represented with an 8-byte data type.

However, the sample 2 output $357335535573573353577573355337$ cannot be represented with an 8-byte data type.

Examples3

Example 1
Input
```
9 1
```
Expected output
```
777777777
```

Example 2

Input

30 125527562340212

Expected output

357335535573573353577573355337

Example 3
Input
```
29 96511468169355
```
Expected output
```
3
```