题目描述

有一个长度为$n$的正整数数组,从数组中截取子段,要求子段和是质数,有多少种截取方案?

名词解释:

子段:序列中连续的一段

子段和:子段中所有元素的总和

输入格式

第一行是一个整数$n$

第二行是$n$个整数$a_i$

输出格式

输出一个整数,代表方案总数

样例输入/输出

4
2 3 5 7

6

6
1 2 3 4 5 6

7

样例解释:

样例1: (2),(3),(5),(7),(2+3=5),(2+3+5+7=17) 6种

样例2:(2),(3),(5),(5+6=11),(1+2=3),(2+3=5),(3+4=7) 7种

数据规模与提示

有3组数据:$n \leq 10^2,a_i \leq 10^2$

另外有2组数据:$n \leq 10^2,a_i \leq 10^{5}$

另外有3组数据:$n \leq 10^3,a_i \leq 10^{2}$

另外有2组数据:$n \leq 10^3,a_i \leq 10^{5}$

时间限制：1s.

内存限制：128MB.