3 and 7

Given a positive integer n, determine whether you can make n by summing up some non-negative multiple of 3 and some non-negative multiple of 7.

Constraints

• n < 2 ** 31

https://binarysearch.com/problems/3-and-7

Examples

Example 1

Input

• n = 13

Output

• answer = True

Explanation

We can get 13 with 1 _ 7 + 2 _ 3.

Example 2

Input

• n = 9

Output

• answer = True

Explanation

We can get 9 with 3 3s.

Solution