A ground station keeps one long recorded tape of bits for a satellite -- a string of characters 0 and 1. Mission control numbers every orbital pass starting at 1, and writes each pass number in plain binary with no leading zero. Before archiving the tape, engineers want to confirm it already contains, as one contiguous run of bits somewhere on the tape, the binary form of every pass number from 1 through n. Determine whether the tape provides that coverage.

Input format

• Line 1: the tape s, a string made only of the characters 0 and 1.
• Line 2: a single integer n.

Output format

Print true if the binary representation (no leading zeros) of every integer from 1 to n appears somewhere in s as a contiguous substring, and false otherwise.

Constraints

• 1 <= |s| <= 1000, and every character of s is 0 or 1.
• 1 <= n <= 100000.

11010
3

true

11010
5

false