Prime Check (Hard Version)

Problem Description

Given a positive integer $n$, determine whether it is a prime number. If it is prime, print $1$; otherwise print $0$. (There may be very large primes.)

(Terminology: a prime number is a natural number greater than $1$ that has no divisors other than $1$ and itself.)

Input Format

The input consists of one line containing a positive integer $n$.

Output Format

Print one line containing a single integer, $1$ or $0$, indicating whether $n$ is prime.

Sample Input

7

Sample Output

1

Constraints

$1 < n < 10^{10}$