만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

지루한 수업과 정사각형 네 개

시간 제한1초메모리 제한1024 MB

요약
M×N 격자 용지의 네 모서리에 정사각형을 하나씩 그려 서로 겹치지 않는 경우의 수를 10^9+7로 나눈 나머지로 구합니다.
난이도

보통10점 중 7점

유형
수학, 조합론
정답자
아직 제출이 없습니다

문제

Juku는 수업이 지루해서 모눈종이에 정사각형을 그린다. 정확히 말하면, 그는 종이마다 정사각형을 네 개씩 그리며, 각 정사각형은 종이의 네 모서리 중 한 곳에 하나씩 놓는다. 정사각형끼리는 겹치지 않는다(다만 맞닿을 수는 있다). Juku는 매번 결과가 이전의 모든 결과와 달라지도록 정사각형을 그리려고 한다. 이 방식으로 종이를 몇 장까지 쓸 수 있는가?

입력

텍스트 파일의 한 줄에 두 정수 MM과 NN (2≤M≤1072 \le M \le 10^7, 2≤N≤1072 \le N \le 10^7)이 주어진다. 이는 Juku가 가진 모눈종이의 크기이다.

출력

텍스트 파일의 한 줄에 정수 하나를 출력한다. 이는 겹치지 않는 정사각형 네 개를 그리는 방법의 수이다. 경우의 수가 매우 많을 수 있고 Juku의 공책도 아주 두꺼우므로, 답은 109+710^9 + 7로 나눈 나머지로 출력한다.

예제3

  1. 예제 1

    입력
    2 2
    
    예상 출력
    1
    
  2. 예제 2

    입력
    3 4
    
    예상 출력
    9
    
  3. 예제 3

    입력
    512 512
    
    예상 출력
    556445640