Count Prime Subsequences

Given an integer \( n \) and an array of \( n \) integers, your task is to count the number of non-empty subsequences that consist entirely of prime numbers. A subsequence here means any subset of the prime elements (order does not matter).

The answer can be computed using the formula \(2^m - 1\), where \( m \) is the number of prime numbers in the array.

Example: For an array [2, 3, 4, 6], there are 2 primes (2 and 3). Hence, the number of valid subsequences is \(2^2 - 1 = 3\).

inputFormat

The first line contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers.

outputFormat

Output a single integer: the number of non-empty subsequences consisting solely of prime numbers.

4
2 3 4 6

3