New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Anuj and Subsets

Contributed by

Jaypal Mudaliyar

Easy

0/40

Avg time to solve 15 mins

Success Rate 85 %

0 upvotes

Problem Statement

Today is Anuj’s birthday and as he is fond of even numbers his friends gifted him with an array ‘ARR’ of ‘N’ positive integers.

Now being fond of even numbers he wanted to make a non-empty sequence out of the original array ‘ARR’, which only includes even numbers. To make the sequence he can delete any elements from the array and then concatenate the remaining elements in order.

But as he loves every even number equally he can’t decide which sequence to pick, Hence being his friend he asked you to find the count of sequences that only consists of even numbers so that he can make a detailed decision of which sequence to pick. Can you help him?

The answer can be very huge, so print the answer modulo 10⁹+7.

EXAMPLE :

Input: ‘N’ = 3, ‘ARR’ = {2, 5, 8}

Output: 3
In this case, there are ‘3’ possible even sequences i.e. [2], [8], and [2, 8].

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The first line will contain the integer ‘T’, the number of test cases.

Each test case consists of two lines.

The first line of input contains one integer, ‘N’, the length of the array ‘ARR’.

Followed by a line containing space-separated ‘N’ positive integers, denoting the elements of the array.

Output format :

For each test case, print the number of non-empty even sequences that can be formed by using the elements of the given array.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘ARR[i]’ <= 10^9
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

3
7

Explanation Of Sample Input 1 :

For the first test case, the even elements of the array ‘ARR’ are [2, 4]. Hence the non-empty even sequences are - [2], [4], [2, 4].

Hence, the output will be: 3

For the second test case, the even elements of the array ‘ARR’ are [2, 2, 6]. Hence the non-empty even sequences are - [2], [2], [6], [2, 2], [2, 6], [2, 6], [2, 2, 6].

Hence, the output will be: 7

Sample Input 2 :

2
10
16 4 12 6 10 2 18 2 14 20
8
1 5 3 9 7 5 3 11

Sample Output 2 :

1023
0

Auto

Console