새로운 AVL 트리 만들기

AVL 트리는 이를 만든 Adelson-Velsky와 Landis의 이름을 딴 트리이다.

AVL 트리를 정의하기 위해 먼저 노드마다 "균형값"을 정의한다. 어떤 노드의 균형값은 왼쪽 서브트리의 높이를 $h_l$, 오른쪽 서브트리의 높이를 $h_r$이라고 할 때 $h_r-h_l$이다. 왼쪽 또는 오른쪽 자식이 없으면 해당 방향 서브트리의 높이는 $0$으로 본다. 원래 AVL 트리는 모든 노드의 균형값이 $-1$, $0$, $1$ 중 하나이다.

MatKor 자료구조 세미나를 들은 민재는 자신의 이름을 넣어 AVLM 트리를 개발하려고 한다. 민재는 노드의 균형값으로 $-1$, $0$, $1$ 중 일부만 허용하고자 한다. 그래서 $\{-1,0,1\}$의 공집합이 아닌 부분집합 $S$를 정하고, 리프 노드를 제외한 모든 노드의 균형값이 $S$의 원소 중 하나인 트리를 AVLM 트리라고 정의했다. 리프 노드의 균형값은 반드시 $0$이므로 리프 노드는 이 조건에서 예외로 둔다.

집합 $S$와 AVLM 트리의 높이 $h$가 주어졌을 때, 높이가 $h$인 AVLM 트리의 모양이 몇 가지인지 구하라.

노드 하나만 있는 트리의 높이는 $1$이다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 10^6$)

각 테스트 케이스는 두 줄로 주어진다. 첫 번째 줄에는 높이 $h$와 $S$의 원소의 개수 $\lvert S \rvert$가 공백으로 구분되어 주어진다. ($1\le h\le 10^6$, $1\le\lvert S \rvert\le 3$)

두 번째 줄에는 노드별로 가능한 균형값인 $S$의 서로 다른 원소 $\lvert S \rvert$개가 오름차순으로 주어진다.

$S$는 $\{-1\}$, $\{0\}$, $\{1\}$, $\{-1,0\}$, $\{-1,1\}$, $\{0,1\}$, $\{-1,0,1\}$ 중 하나이다.

같은 테스트 케이스는 여러 번 주어지지 않는다.

각 테스트 케이스마다 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

입력이 많은 경우 빠른 입출력을 사용하지 않으면 시간 초과가 나올 수 있다.