You are given a variety of integers b1,b2,… ,bn. A cluster a1,a2,… ,an of integers is half and half if for every I (1≤i≤n) no less than one of these conditions is valid: bi=ai, or bi=∑ij=1aj. Track down the number
Correct answer will be upvoted else downvoted. Computer science.
You are given a variety of integers b1,b2,… ,bn.
A cluster a1,a2,… ,an of integers is half and half if for every I (1≤i≤n) no less than one of these conditions is valid:
bi=
bi=∑ij=1aj.
Track down the number of half breed clusters a1,a2,… ,an. As the outcome can be extremely huge, you should print the appropriate response modulo 109+7.
Input
The principal line contains a solitary integer t (1≤t≤104) — the number of experiments.
The principal line of each experiment contains a solitary integer n (1≤n≤2⋅105).
The second line of each experiment contains n integers b1,b2,… ,bn (−109≤bi≤109).
It is ensured that the amount of n for all experiments doesn't surpass 2⋅105.
Output
For each experiment, print a solitary integer: the number of half and half exhibits a1,a2,… ,a modulo 109+7.
Step by step
Solved in 4 steps with 1 images