Subsequence-Numbers Divisible by 7 CodeChef Solution | CodeChef Problem Solution 2022

Subsequence-Numbers Divisible by 7 CodeChef Solution | CodeChef Problem Solution 2022

Kulyash has given you an array A$A$ of size N$N$.

He defines the subsequence-number of a non-empty subsequence S$S$ of array A$A$ as the number formed by the concatenation of all the elements of the subsequence S$S$.

Find the count of non-empty subsequences of A$A$ having their subsequence-numbers divisible by 7$7$. Since the answer can be huge, output it modulo 109+7${10}^9+7$.

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 S$S$ of A$A$ is [2,5,7,10]$[2,5,7,10]$. The subsequence-number of this subsequence is 25710$25710$.

Solution Click Below:-  CLICK HERE

Input Format

• The first line will contain T$T$, the number of test cases. Then the test cases follow.
• The first line of each test case contains one integer N$N$, the size of the array.

Xor Palindrome CodeChef Solution

Total Prize Money CodeChef Solution

Subsequence-Numbers Divisible by 7 CodeChef Solution

Subarrays with length CodeChef Solution

Practice makes us perfect CodeChef Solution

Score High CodeChef Solution

Make them Zero CodeChef Solution

Degree of Polynomial CodeChef Solution

• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ — the elements of the array A$A$.

Output Format

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

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤3⋅105$1\le N\le 3\cdot {10}^5$
• 1≤Ai≤3⋅105$1\le A_i\le 3\cdot {10}^5$
• Sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$