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

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

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

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

박승원은 이 JOI 로고를 본딴 "프랙탈 박승원"을 프로필 사진으로 만들어 사용한다. 이에 감명을 받은 빅승윈은 프랙탈 박승원에 사용되는 타일을 만드는 공장을 건설했다. 물론 무한히 작은 타일을 만들 수는 없기 때문에, 다음과 같이 네 종류의 1×1 타일, 세 종류의 2×2 타일, 그리고 세 종류의 4×4 타일을 제작한다.

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

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

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

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

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