407099: GYM102697 070 Mersenne Primes

070. Mersenne Primestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

As you may know, large prime numbers are in very high demand currently, and there are many large scale searches for even larger primes. Some of the largest prime numbers discovered fit a number called a Mersenne Prime, which is essentially any prime number than can be represented by the equation $$$2^{p}-1$$$. Mersenne Primes are especially interesting as they can be tested for primality with a special test called the Lucas-Lehmer test. Although you could technically solve Mersenne Primes using typical prime-number algorithms, the Lucas-Lehmer test will almost always be faster. The pseudocode for conducting the Lucas-Lehmer test for as found on Wikipedia is as follows:

This code will test $$$p$$$ as $$$p$$$ is found in the equation $$$2^{p}-1$$$. As a result, Mersenne Primes are often referred to with this value of $$$p$$$ that is present in the power of two. Your task is to implement the Lucas-Lehmer test so that you can determine if given values of $$$p$$$ are valid Mersenne Primes. Some of the values of $$$p$$$ might cause the values in the Lucas-Lehmer test to be greater than 32 or 64 bits, so arbitrary precision might be required(BigInteger class in Java).Input

A single integer $$$p$$$ that represents the power of 2 in the equation $$$2^{p}-1$$$ to be tested.

Output

The phrase "true" should be printed if the value calculated with $$$p$$$ is a Mersenne Prime, and the phrase "false" should be printed otherwise.

ExamplesInput

7

Output

true

Input

15

Output

false

Note

More information regarding the Lucas-Lehmer test and Mersenne Primes can be found here: https://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test, https://en.wikipedia.org/wiki/Mersenne_prime.