문제를 푸는 문제 (박승원)

이 문제에는 제출할 수 없다. "문제를 푸는 문제" 문제를 참조하라.

박승원은 이 문제를 풀지 못했다.

일본정보올림피아드의 로고가 프랙탈을 이룬다는 사실을 아는가?

박승원은 JOI 로고를 본뜬 "프랙탈 박승원"을 프로필 사진으로 쓴다. 이에 감명을 받은 빅승윈은 프랙탈 박승원에 쓰일 타일을 만드는 공장을 세웠다. 무한히 작은 타일은 만들 수 없으므로, 다음과 같이 네 종류의 $1 \times 1$ 타일, 세 종류의 $2 \times 2$ 타일, 세 종류의 $4 \times 4$ 타일을 만든다.

그로부터 오랜 세월이 흘렀다. 2030년, 박승원 타일 공장은 이제 $Ve$종류의 $1 \times 1$ 타일, $Yd$종류의 $2 \times 2$ 타일, $Pz$종류의 $4 \times 4$ 타일을 만든다. 오늘 박승원은 빅승윈에게서 각 종류의 타일을 $10^{18}$개씩 구매했다. 박승원은 이 타일을 사용해서 $n \times m$ 격자를 채우려고 한다. 격자를 채울 때 사용한 타일은 격자의 칸에 완전히 들어맞아야 하고, 각 칸은 정확히 한 타일이 차지해야 한다. 박승원은 격자를 채우는 방법의 수가 궁금해졌다.

하지만, 박승원은 이 문제를 풀지 못했다.

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

각 테스트케이스는 한 줄로 이루어져 있으며, $n$, $m$, $Ve$, $Yd$, $Pz$가 주어진다. ($1 \le n, m \le 10$; $0 \le Ve, Yd, Pz \le 10^9$)

격자를 채우는 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.