Igav tund nelja ruuduga

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

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

어려움10점 중 8점

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

문제

Jukul on tunnis igav ja ta joonistab ruudulisele paberile ruute. Täpsemalt joonistab ta igale paberile alati neli ruutu, ühe igasse paberi nurka, niiviisi, et ruudud ei kattu omavahel (aga nad võivad kokku puutuda). Juku proovib ruute joonistada nii, et iga tulemus oleks eelmistest erinev. Mitu paberilehte on tal võimalik sel viisil ära kulutada?

입력

Tekstifaili ainsal real on kaks arvu MM ja NN (2≤M≤1072 \le M \le 10^7, 2≤N≤1072 \le N \le 10^7), mis näitavad Juku ruudulise paberi mõõtmeid.

출력

Tekstifaili ainsale reale väljastada üks täisarv: erinevate nelja mitte\-kattuva ruudu joonistamise võimaluste arv. Kuna võimalusi võib olla palju (ja Jukul on erakordselt paks vihik), anda vastus mooduli 109+710^9 + 7 järgi.

예제3

  1. 예제 1

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

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

    입력
    512 512
    
    예상 출력
    556445640