준영이

• 초콜렛의 크기 N*M가 x라고 했을때, 크기가 같지만 모양이 1*x 인 초콜렛을 생각해보자. 이 초콜렛은 원하는 면적대로 나눌수 있으니까, 결국 어떤수 x를 곱이 최대가 되도록 분할하는 문제가 된다.
• 합이 일정하고 곱이 최대가 되도록 분할하는 방법은, 2와 3만으로 분할하되 3의 갯수가 최대가 되도록 하는 것이 최선이라는 것을 알고 있다 (1437 과 같은 문제.). x%3 에 따라서, 2를 0~2개 포함해주고 나머지를 전부 3으로 나누면 된다.
• 하지만, 원래 문제에도 이 방법을 그대로 적용하기 위해서는, 직사각형 모양에서도 위의 방법으로 분할하는 것이 항상 가능하다는 것에 대한 증명이 필요하다.
  • x%3==0 인 경우는 N또는 M이 3의 배수이다. N이 3의 배수라 하면, 1*N 짜리 조각 M개로 나눈 다음에, 각각의 1*N 조각을 다시 1*3 조각으로 나누면 된다
  • x%3==2 인 경우는 N과 M이 각각 3k+1, 3l+2의 형태가 된다. 3k*(3l+2) 조각과 1*(3l+2) 조각으로 나누면, 앞의 조각은 쉽게 1*3들로 나눌수 있고, 뒤의 조각은 1*2 하나과 1*3들로 나눌수 있다
  • x%3==1 인 경우는 N과 M이 3k+1, 3l+1이거나 3k+2, 3l+2이다. 앞의 경우에는 1*(3l+1)조각을 1*2 두개와 1*3들로 나눌수 있고, 뒤의 경우에는 2*(3l+2) 를 다시 2*2와 2*3l 로 나누면 역시 1*2 두개와 1*3들로 나눌수 있다

"""Solution code for "BOJ 31443. 준영이".

- Problem link: https://www.acmicpc.net/problem/31443
- Solution link: http://www.teferi.net/ps/problems/boj/31443

Tags: [ad hoc]
"""

MOD = 10**9 + 7


def main():
    N, M = [int(x) for x in input().split()]

    a = N * M
    if a == 1:
        print('1')
    elif a % 3 == 0:
        print(pow(3, a // 3, MOD))
    elif a % 3 == 2:
        print(2 * pow(3, (a - 2) // 3, MOD) % MOD)
    elif a % 3 == 1:
        print(2 * 2 * pow(3, (a - 4) // 3, MOD) % MOD)


if __name__ == '__main__':
    main()