시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

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


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

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

박승원은 이 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로 나눈 나머지를 출력한다.

서브태스크 1 (172645134점)

Yd = Pz = 0

서브태스크 2 (488967702점)

m ≤ 3

서브태스크 3 (652141864점)

Pz = 0

서브태스크 4 (833728947점)

추가 제약 조건이 없다.

예제 입력 1

5
2 1 2 0 0
5 3 1 1 1
2 4 2 1 0
4 4 1 1 1
10 10 4 3 3

예제 출력 1

4
21
305
36
6910035

출처

Contest > 구데기컵 > 진짜 최종 구데기컵 2 🎁번

채점

  • 예제는 채점하지 않는다.