070. Mersenne Primes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Examples
Input
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.