N-beat

N-beat는 인기 있는 리듬 아케이드 게임이다. 플레이어는 $x \times y$ 격자에 배열된 버튼을 누른다. 버튼은 눌러야 할 때 켜지며, 점수를 얻으려면 정확한 타이밍에 눌러야 한다.

한 번의 N-beat 게임은 하나 이상의 화면으로 이루어진다. 화면은 눌러야 할 켜진 버튼들의 배치다.

위 그림은 $4 \times 4$ 격자를 가진 N-beat 기계의 연속된 화면 4개를 보여 준다. 표적 표시가 있는 상자가 눌러야 할 켜진 버튼이다.

게임에서 화면이 이어진 순서를 전사(transcription)라고 한다.

작곡가 Jaeha Koo가 N-beat의 새 곡을 만들었다. 당신은 이 곡의 전사를 만들려고 한다.

곡에는 $B$개의 박자가 있으므로 전사는 $B$개의 화면으로 이루어진다. 제한이 없다면 가능한 전사는 모두 $(2^{xy})^B$개다.

전사마다 난이도가 다르다. 버튼은 손가락 하나로 하나씩 누르므로, 켜진 버튼이 많은 화면일수록 어렵다. 켜진 버튼이 10개를 넘는 화면은 성공적으로 누르기가 매우 어렵다. 인접한 화면에 켜진 버튼이 많아도 게임이 어려워진다. 예를 들어 켜진 버튼이 각각 7개와 6개인 연속 두 화면은, 2개와 8개인 두 화면보다 더 어려울 수 있다.

관대한 전사 작성자로서 당신은 켜지는 버튼 수에 제한을 두기로 했다. 제한은 세 개의 음이 아닌 정수 $p_1$, $p_2$, $p_3$로 주어진다. $p_1$은 어떤 화면에서든 켜진 버튼의 최대 개수다. $p_2$는 연속된 두 화면에서 켜진 버튼의 최대 개수다. $p_3$는 연속된 세 화면에서 켜진 버튼의 최대 개수다. 위 그림의 4개 화면은 켜진 버튼이 각각 4, 8, 6, 8개이므로, 이 전사는 $p_1 \ge 8$, $p_2 \ge 14$, $p_3 \ge 22$일 때만 유효하다.

당신의 과제는 주어진 $x$, $y$, $B$, $p_1$, $p_2$, $p_3$에 대해 가능한 전사의 수를 세는 것이다. 결과가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

입력은 $T$개의 테스트 케이스로 이루어진다. 첫 줄에 $T$가 주어진다.

각 테스트 케이스는 공백으로 구분된 여섯 정수로 이루어진 한 줄이다. 순서대로 $x$, $y$ ($1 \le x, y \le 1000$), $B$ ($1 \le B \le 10^9$), $p_1$ ($0 \le p_1 \le 10$), $p_2$ ($0 \le p_2 \le 20$), $p_3$ ($0 \le p_3 \le 30$)이다.

각 테스트 케이스마다 가능한 전사의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.