Prime Subset Sums

Let S = {2, 3, 5, ..., 4999} be the set of prime numbers less than 5000.

Find the number of subsets of S, the sum of whose elements is a prime number. Enter the rightmost 16 digits as your answer.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter