249 : 素数の部分集合和

S = {2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする。

要素の合計が素数となるような, S の部分集合の個数を求めよ。 最下位の 16 桁を答えとして入力せよ。