$2$

You are given an integer $N.$ A string consisting of the lowercase English alphabet is called valld ifand only if each vowel occurs at most once in the string.

Each vowel is assigned a score which is given by a score array of size $5$ where,

score$[0]$ refers to the score of a

score$[1]$ refers to the score of $e$

score$[2]$ refers to the score of $i$

score$[3]$ refers to the score of $o$

score$[4]$ refers to the score of $u.$

The FUN of a string is defined as the sum of the product of the score of two consecutive vowels and their distance.

Your task is to find the sum of FUN of all possible valid strings of length $N$ and return the ans modulo ${10}^{n}9+7.$

Input Format

The first line contains $T$ denoting the number of test cases. $T$ also Specifies the number of times you have to run the countThemA$/$I function on a different set of inputs.

For each test case:

The first line contains $N$ denoting the length of the string.

The second line contains $5$ space$-$separated values denoting the scores of the vowels.

Output Format

For each test case, print the total FUN modulo ${10}^{n}O+7$ in a new line.

imple Testcase #$0$

estcase Input

Copy