New AVL Tree

The AVL tree is named after Adelson-Velsky and Landis, who created it.

To define an AVL tree, first define the "balance value" of each node. The balance value of a node is $h_r-h_l$, where $h_l$ is the height of its left subtree and $h_r$ is the height of its right subtree. If the node has no left or right child, the height of that subtree is taken as $0$. In a regular AVL tree, every node has a balance value of $-1$, $0$, or $1$.

Minjae, who attended the MatKor data structures seminar, wants to develop an AVLM tree named after himself. He allows only some of the values $-1$, $0$, and $1$ as balance values. He picks a nonempty subset $S$ of $\{-1,0,1\}$ and defines an AVLM tree as a tree in which every node except the leaves has a balance value that is an element of $S$. Leaves are exempt because their balance value is always $0$.

Given the set $S$ and a height $h$ of an AVLM tree, count the number of possible tree shapes of height $h$.

A tree with a single node has height $1$.

The first line contains the number of test cases $T$. ($1\le T\le 10^6$)

Each test case consists of two lines. The first line contains the height $h$ and the number of elements $\lvert S \rvert$, separated by a space. ($1\le h\le 10^6$, $1\le\lvert S \rvert\le 3$)

The second line contains the $\lvert S \rvert$ distinct elements of $S$, which are the allowed balance values of the nodes, in ascending order.

The set $S$ is one of $\{-1\}$, $\{0\}$, $\{1\}$, $\{-1,0\}$, $\{-1,1\}$, $\{0,1\}$, $\{-1,0,1\}$.

Each test case appears only once.

For each test case, print the answer modulo $10^9+7$ on its own line.

Reading input with fast I/O is necessary when there are many test cases, or the program may exceed the time limit.