# Subsequence-Numbers Divisible by 7 solution codechef

## Subsequence-Numbers Divisible by 7 solution codechef

Kulyash has given you an array AA of size NN.

He defines the subsequence-number of a non-empty subsequence SS of array AA as the number formed by the concatenation of all the elements of the subsequence SS.

Find the count of non-empty subsequences of AA having their subsequence-numbers divisible by 77. Since the answer can be huge, output it modulo 109+7109+7.

• Discover & apply to 20M+ jobs/internships on LinkedIn
• Reach out to hiring managers/recruiters/mentors directly
• Find career paths that people similar to them have taken
• Learn from over 17K expert-led LinkedIn Learning courses (technical & soft-skills) with certificates

For example: Consider A=[1,2,3,4,5,6,7,8,9,10]A=[1,2,3,4,5,6,7,8,9,10]. A subsequence SS of AA is [2,5,7,10][2,5,7,10]. The subsequence-number of this subsequence is 2571025710.

### Input Format

• The first line will contain TT, the number of test cases. Then the test cases follow.
• The first line of each test case contains one integer NN, the size of the array.
• The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN — the elements of the array AA.

### Output Format

For each test case, output in a single line the number of subsequences with subsequence-number divisible by 77 modulo 10000000071000000007.

## Subsequence-Numbers Divisible by 7 solution codechef

• 1T10001≤T≤1000
• 1N31051≤N≤3⋅105
• 1Ai31051≤Ai≤3⋅105
• Sum of NN over all test cases does not exceed 31053⋅105

### Sample Input 1

3
2
1 2
4
1 2 3 4
2
7 7


### Sample Output 1

0
1
3


## Subsequence-Numbers Divisible by 7 solution codechef

Test case 11: Only 33 subsequences are possible for the given array. These are [1,2][1,2], and . The subsequence-numbers are 111212, and 22 respectively. None of the subsequence-numbers are divisible by 77, so the answer is 00.

Test case 22: [1,4][1,4] is the only subsequence having its subsequence-number 1414 which is divisible by 77. So, the answer is 11.

Test case 33: All the non-empty subsequences , and [7,7][7,7] have their subsequence-numbers 7,7,7,7, and 7777 divisible by 77. So, the answer is 33.