Problem:


Score: 900 points

Problem Statement

In 2937, DISCO creates a new universe called DISCOSMOS to celebrate its 1000-th anniversary.

DISCOSMOS can be described as an H \times W grid. Let (i, j) (1 \leq i \leq H, 1 \leq j \leq W) denote the square at the i-th row from the top and the j-th column from the left.

At time 0, one robot will be placed onto each square. Each robot is one of the following three types:

Type-H: Does not move at all.

Type-R: If a robot of this type is in (i, j) at time t, it will be in (i, j+1) at time t+1. If it is in (i, W) at time t, however, it will be instead in (i, 1) at time t+1. (The robots do not collide with each other.)

Type-D: If a robot of this type is in (i, j) at time t, it will be in (i+1, j) at time t+1. If it is in (H, j) at time t, however, it will be instead in (1, j) at time t+1.

There are 3^{H \times W} possible ways to place these robots. In how many of them will every square be occupied by one robot at times 0, T, 2T, 3T, 4T, and all subsequent multiples of T?

Since the count can be enormous, compute it modulo (10^9 + 7).

Constraints

1 \leq H \leq 10^9

1 \leq W \leq 10^9

1 \leq T \leq 10^9

H, W, T are all integers.

Input

Input is given from Standard Input in the following format:

H W T

Output

Print the number of ways to place the robots that satisfy the condition, modulo (10^9 + 7).

Sample Input 1

2 2 1

Sample Output 1

9

Shown below are some of the ways to place the robots that satisfy the condition, where ., >, and v stand for Type-H, Type-R, and Type-D, respectively:

>>  ..  vv
..  ..  vv

Sample Input 2

869 120 1001

Sample Output 2

672919729



Sample input:
2 2 1


Sample output:
9

Submission status: Wrong Answer

Solution code:
H, W, T = map(int, input().split())
H_pace = T % H
W_pace = T % W
H_list,W_list = [],[]
H_count,W_count = 0,0
for i in range(0, H):
	if i*H_pace % H not in H_list:
		H_list += [i*H_pace % H]
		H_count += 1
for i in range(0, W):
	if i*W_pace % W not in W_list:
		W_list += [i*W_pace % W]
		W_count += 1

ans = 0
if H_count % W_count == 0:
	ans += 1
	for i in range(2,int(W_count/2)+2):
		if W_count % i == 0:
			ans += 1
elif W_count % H_count == 0:
	ans += 1
	for i in range(2,int(H_count/2)+2):
		if H_count % i == 0:
			ans += 1
ans = (ans + (2**W_count + 2**H_count - 1)) % (10**9 + 7)
ans = ans ** int(H/H_count) % (10**9 + 7)
ans = ans ** int(W/W_count) % (10**9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
mod=10**9+7
h,w,t=map(int,input().split())
groups=gcd(h,t)*gcd(w,t)
unit=(h//gcd(h,t),w//gcd(w,t))
cnt=(2**(unit[0])+2**(unit[1])-1)%mod
unitd=gcd(unit[0],unit[1])
if unitd==1:
  pass
elif unitd==2:
  cnt+=2
  cnt%=mod
elif unitd%2==0:
  cnt+=2+2*unitd
  cnt%=mod
else:
  cnt+=unitd*2
  cnt%=mod
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
print(pow_r(cnt,groups))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
mod=10**9+7
h,w,t=map(int,input().split())
groups=gcd(h,t)*gcd(w,t)
unit=(h//gcd(h,t),w//gcd(w,t))
cnt=(2**(unit[0])+2**(unit[1])-1)%mod
unitd=gcd(unit[0],unit[1])
if unitd==1:
  pass
elif unitd==2:
  cnt+=2
  cnt%=mod
elif unitd%2==0:
  cnt+=2+2*unitd
  cnt%=mod
else:
  cnt+=unitd*2
  cnt%=mod
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)%mod
print(pow_r(cnt,groups))

Submission status: Wrong Answer

Solution code:
import fractions
h,w,t=map(int,input().split())
g=fractions.gcd(h,w)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
H=fractions.gcd(h,t)
W=fractions.gcd(w,t)
p=10**9+7
a=power_func(2,g,p)
b=power_func(2,h//H,p)
c=power_func(2,w//W,p)
d=(a+b+c-3)%p
print(power_func(d,H*W,p))

Submission status: Wrong Answer

Solution code:
import fractions
h,w,t=map(int,input().split())
g=fractions.gcd(h,w)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
p=10**9+7
a=power_func(2,g,p)
b=power_func(2,h,p)
c=power_func(2,w,p)
print((a+b+c-3)%p)

Submission status: Wrong Answer

Solution code:
import fractions
h,w,t=map(int,input().split())
g=fractions.gcd(h,w)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
p=10**9+7
a=power_func(2,g,p)
b=power_func(2,h,p)
c=power_func(2,w,p)
print(a+b+c-3)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)
    
H,W,T=map(int,input().split())
mod=10**9+7

h=gcd(H,T)
w=gcd(W,T)
H//=h
W//=w

print(h,w,H,W)
ans=pow(2,H,mod)+pow(2,W,mod)+pow(2,gcd(H,W),mod)-3
print(pow(ans,h*w,mod))

Submission status: Wrong Answer

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( 2 ** ( H // htgcd) + 2 ** (W // wtgcd) - 1)
if (H // htgcd) % 2 == 0 and (W // wtgcd) % 2 == 0:
    p += 2

#print (p,n)

ans = power(p , n)

print (ans)

Submission status: Wrong Answer

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( power(2 , H // htgcd) + power(2 , W // wtgcd) - 1)
if (H // htgcd) % 2 == 0 and (W // wtgcd) % 2 == 0:
    p += 2


ans = power(p , n)

print (ans)

Submission status: Wrong Answer

Solution code:
print("I never do this problem")

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#m = int(input())
h,w,t = [int(i) for i in readline().split()]

MOD = 10**9+7
from fractions import gcd

gh = gcd(h,t)

gw = gcd(w,t)

c = h//gh * w//gw

ans = pow(2,w//gw,MOD) + pow(2,h//gh,MOD)  - 1

d = 0
if h//gh%2 and w//gw%2:
    d = pow(2,gcd(h//gh,w//gw),MOD)
    
ans += d
print(pow(ans,h*w//c,MOD))

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#m = int(input())
h,w,t = [int(i) for i in readline().split()]

MOD = 10**9+7
from fractions import gcd

gh = gcd(h,t)

gw = gcd(w,t)

c = h//gh * w//gw

ans = pow(2,w//gw,MOD) + pow(2,h//gh,MOD) + (2 if h//gh%2 and w//gw%2 else 0) - 1


print(pow(ans,h*w//c,MOD))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
h,w,t=map(int,input().split())
groups=gcd(h,t)*gcd(w,t)
unit=(h//gcd(h,t),w//gcd(w,t))
cnt=(2**(unit[0])+2**(unit[1])-3)%mod
unitd=gcd(unit[0],unit[1])
cnt+=pow_r(2,unitd)%mod
print(pow_r(cnt,groups))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = (pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W)) - 2) % MOD
print(pow(ans, ga*gb, MOD))

Submission status: Time Limit Exceeded

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( 2 ** ( H // htgcd) + 2 ** (W // wtgcd) - 3)
p += 2 ** fractions.gcd( H // htgcd , W // wtgcd)

#print (p,n)

ans = modpower(p , n)

print (ans)

Submission status: Time Limit Exceeded

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( modpower(2, ( H // htgcd)) + modpower(2, (W // wtgcd)) - 3)
p += modpower(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)

Submission status: Time Limit Exceeded

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( power(2, ( H // htgcd)) + power(2, (W // wtgcd)) - 3)
p += power(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)

Submission status: Time Limit Exceeded

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( power(2, ( H // htgcd)) + power(2, (W // wtgcd)) - 3)
p += power(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)

Submission status: Accepted

Solution code:
from fractions import gcd
H,W,T=map(int, input().split())
gh, gw = gcd(H, T), gcd(W, T)
h, w = H // gh, W // gw
MOD = 1000000007
print(pow(pow(2, h, MOD) + pow(2, w, MOD) + pow(2, gcd(h, w), MOD) - 3, gh * gw, MOD))

Submission status: Accepted

Solution code:
def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
H,W,T=map(int, input().split())
gh, gw = gcd(H, T), gcd(W, T)
h, w = H // gh, W // gw
MOD = 1000000007
print(pow(pow(2, h, MOD) + pow(2, w, MOD) + pow(2, gcd(h, w), MOD) - 3, gh * gw, MOD))

Submission status: Accepted

Solution code:
from fractions import gcd
MOD = 1000000007
def pw(x, y):
    ans = 1
    while y > 0:
        if y % 2:
            ans = ans * x % MOD
        x = x * x % MOD
        y //= 2
    return ans
H, W, T = map(int, input().split())
HT = gcd(H, T)
WT = gcd(W, T)
H //= HT
W //= WT
print(pw(pw(2, H) + pw(2, W) + pw(2, gcd(H, W)) - 3, HT * WT))

Submission status: Accepted

Solution code:
mod=10**9+7
from fractions import gcd
h,w,t=map(int,input().split())
gh,gw=gcd(h,t),gcd(w,t)
h1,w1=h//gh,w//gw
print(
		pow(
			pow(2,w1,mod)+
			pow(2,h1,mod)+
			(mod-1)+
			pow(2,gcd(h1,w1),mod)+mod-2
			,gh*gw,mod)
		)

Submission status: Accepted

Solution code:
def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

mod = 1000000007
H, W, K = map(int, input().split())
gh = gcd(H, K); rh = H // gh
gw = gcd(W, K); rw = W // gw
sub = pow(2, rh, mod) + pow(2, rw, mod) + pow(2, gcd(rh, rw), mod) - 3
ans = pow(sub, gh * gw, mod)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
h,w,t=map(int,input().split())
H=gcd(h,t);W=gcd(w,t)
groups=H*W
unit=(h//H,w//W)
cnt=(pow_r(2,unit[0])+pow_r(2,unit[1])-3)%mod
unitd=gcd(unit[0],unit[1])
cnt+=pow_r(2,unitd)%mod
print(pow_r(cnt,groups))

Submission status: Accepted

Solution code:
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2%mod, (n - 1) // 2)%mod
h,w,t=map(int,input().split())
H=gcd(h,t);W=gcd(w,t)
groups=H*W
unit=(h//H,w//W)
cnt=(2**(unit[0])+2**(unit[1])-3)%mod
unitd=gcd(unit[0],unit[1])
cnt+=pow_r(2,unitd)%mod
print(pow_r(cnt,groups))

Submission status: Accepted

Solution code:
import fractions
h,w,t=map(int,input().split())
g=fractions.gcd(h,w)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
H=fractions.gcd(h,t)
W=fractions.gcd(w,t)
p=10**9+7
a=power_func(2,fractions.gcd(h//H,w//W),p)
b=power_func(2,h//H,p)
c=power_func(2,w//W,p)
d=(a+b+c-3)%p
print(power_func(d,H*W,p))

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)
    
H,W,T=map(int,input().split())
mod=10**9+7

h=gcd(H,T)
w=gcd(W,T)
H//=h
W//=w

ans=pow(2,H,mod)+pow(2,W,mod)+pow(2,gcd(H,W),mod)-3
print(pow(ans,h*w,mod))

Submission status: Accepted

Solution code:
from fractions import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = (pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W), MOD) - 2) % MOD
print(pow(ans, ga*gb, MOD))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

def gcd(a, b):
    if b == 0: return a
    if (a, b) in memo: return memo[(a, b)]
    res = memo[(a, b)] = gcd(b, a % b)
    return res
memo = {}

def main():
    md = 10 ** 9 + 7
    h, w, t = MI()
    # t=1のパターンに置き換える
    h1 = h // gcd(h, t)
    w1 = w // gcd(w, t)
    ans = (pow(2, h1, md) + pow(2, w1, md) + pow(2, gcd(h1, w1), md) - 3) % md
    # print(ans)
    # t=1のパターンの個数分累乗
    ans = pow(ans, gcd(h, t) * gcd(w, t), md)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))

def gcd(a, b):
    if b == 0: return a
    if (a, b) in memo: return memo[(a, b)]
    return gcd(b, a % b)
memo = {}

def main():
    md = 10 ** 9 + 7
    h, w, t = MI()
    # t=1のパターンに置き換える
    h1 = h // gcd(h, t)
    w1 = w // gcd(w, t)
    ans = (pow(2, h1, md) + pow(2, w1, md) + pow(2, gcd(h1, w1), md) - 3) % md
    # print(ans)
    # t=1のパターンの個数分累乗
    ans = pow(ans, gcd(h, t) * gcd(w, t), md)
    print(ans)

main()

Submission status: Accepted

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = pow( 2, ( H // htgcd) ,mod ) +pow( 2, (W // wtgcd) , mod) - 3
p += pow(2,fractions.gcd( H // htgcd , W // wtgcd),mod)

#print (p,n)

ans = pow( p , n , mod )

print (ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from fractions import gcd
def resolve():
    h,w,t=map(int,input().split())
    g1=gcd(h,t)
    g2=gcd(w,t)
    h=h//g1
    w=w//g2
    ans=pow(2,h,MOD)+pow(2,w,MOD)+pow(2,gcd(h,w),MOD)-3
    ans%=MOD
    print(pow(ans,g1*g2,MOD))
resolve()

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7
n, m, t = map(int, input().split())
a = gcd(n, t)
b = gcd(m, t)
n //= a
m //= b
ret = pow(2, n, mod) + pow(2, m, mod) + pow(2, gcd(n, m), mod) - 3
print(pow(ret, a * b, mod))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#m = int(input())
h,w,t = [int(i) for i in readline().split()]

MOD = 10**9+7
from fractions import gcd

gh = gcd(h,t)

gw = gcd(w,t)

c = h//gh * w//gw

ans = pow(2,w//gw,MOD) + pow(2,h//gh,MOD) + pow(2,gcd(h//gh,w//gw),MOD) - 2 - 1

print(pow(ans,h*w//c,MOD))

Submission status: Accepted

Solution code:
from fractions import gcd
H,W,T=map(int,input().split());M=10**9+7;a=gcd(H,T);b=gcd(W,T);H//=a;W//=b;print(pow(pow(2,H,M)+pow(2,W,M)+pow(2,gcd(H,W),M)-3,a*b,M))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

H,W,T = map(int,read().split())

MOD = 10 ** 9 + 7

a = gcd(H,T); b = gcd(W,T)

H //= a; W //= b

x = pow(2,H,MOD) + pow(2,W,MOD) + pow(2,gcd(H,W),MOD) - 3
answer = pow(x,a*b,MOD)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

H,W,T = map(int,read().split())

MOD = 10 ** 9 + 7

a = gcd(H,T); b = gcd(W,T)

H //= a; W //= b

x = pow(2,H,MOD) + pow(2,W,MOD) + pow(2,gcd(H,W),MOD) - 3
answer = pow(x,a*b,MOD)
print(answer)

Submission status: Runtime Error

Solution code:
from math import gcd
H,W,T=map(int,input().split())
mod=10**9+7
if T%H==0 and T%W==0:
  print(pow(3,H*W,mod))
  exit()
GH=gcd(H,T)
RH=H//GH
GW=gcd(W,T)
RW=W//GW
GA=gcd(GH,GW)
def f(x):
  r=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      if i*i!=x:
        r.append(x//i)
  return r

P=pow(pow(2,RH,mod)+pow(2,RW,mod)-1,GH*GW,mod)
if H==W:
  assert(False)
print(P)

Submission status: Runtime Error

Solution code:
from math import gcd
H,W,T=map(int,input().split())
mod=10**9+7
if T%H==0 and T%W==0:
  print(pow(3,H*W,mod))
  exit()
GH=gcd(H,T)
RH=H//GH
GW=gcd(W,T)
RW=W//GW
GA=gcd(GH,GW)
def f(x):
  r=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      if i*i!=x:
        r.append(x//i)
  return r

P=pow(pow(2,RH,mod)+pow(2,RW,mod)-1,GH*GW,mod)
if H==W:
  assert(False)

Submission status: Runtime Error

Solution code:
from math import gcd
H,W,T=map(int,input().split())
mod=10**9+7
if T%H==0 and T%W==0:
  print(pow(3,H*W,mod))
  exit()
GH=gcd(H,T)
RH=H//GH
GW=gcd(W,T)
RW=W//GW
GA=gcd(GH,GW)
def f(x):
  r=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      if i*i!=x:
        r.append(x//i)
  return r

if H!=W:
  print(pow(pow(2,GH*GW,mod),RW,mod)*pow((pow(2,RH,mod)-1)*pow(pow(500000004,GW,mod),RW,mod)+1,GH,mod)%mod)
  exit()
assert(False)

Submission status: Runtime Error

Solution code:
from fractions import gcd
gh, gw = gcd(H, T), gcd(W, T)
h, w = H // gh, W // gw
MOD = 1000000007
print(pow(pow(2, h, MOD) + pow(2, w, MOD) + pow(2, gcd(h, w), MOD) - 3, gh * gw, MOD))

Submission status: Runtime Error

Solution code:
import math
H,W,T=map(int, input().split())
gh, gw = math.gcd(H, T), math.gcd(W, T)
h, w = H // gh, W // gw
MOD = 1000000007
print(pow(pow(2, h, MOD) + pow(2, w, MOD) + pow(2, math.gcd(h, w), MOD) - 3, gh * gw, MOD))

Submission status: Runtime Error

Solution code:
import math
H,W,T=map(int, input().split())
gh, gw = math.gcd(H, T), math.gcd(W, T)
h, w = H // gh, W // gw
MOD = 1000000007
print(pow(pow(2, h) + pow(2, w) + pow(2, math.gcd(h, w)) - 3, gh * gw, MOD))

Submission status: Runtime Error

Solution code:
from math import gcd
MOD = 1000000007
def pw(x, y):
    ans = 1
    while y > 0:
        if y % 2:
            ans = ans * x % MOD
        x = x * x % MOD
        y //= 2
    return ans
H, W, T = map(int, input().split())
HT = gcd(H, T)
WT = gcd(W, T)
H //= HT
W //= WT
print(pw(pw(2, H) + pw(2, W) + pw(2, gcd(H, W)) - 3, HT * WT))

Submission status: Runtime Error

Solution code:
#!/bin/python3
mod=10**9+7
from math import gcd
h,w,t=map(int,input().split())
gh,gw=gcd(h,t),gcd(w,t)
h1,w1=h//gh,w//gw
print(
		pow(
			pow(2,w1,mod)+
			pow(2,h1,mod)+
			(mod-1)+
			pow(2,gcd(h1,w1),mod)+mod-2
			,gh*gw,mod)
		)

Submission status: Runtime Error

Solution code:
H, W, T = map(int, input().split())
H_count,W_count = 1,1

def getfac(l):
	l_list = []
	for i in range(2, int(l/2)+1):
		if l % i == 0:
			l_list += [i]
	return l_list

def getcnt(l):
	l_list = getfac(l)
	pace = T % l
	pace_list = getfac(pace) 
	re = 1
	if l_list == []:
		re = l
	elif l % pace == 0:
		re = int(l/pace)
	else:
		if pace_list == []:
			re = l
		else:
			for i in l_list:
				if i not in pace_list:
					re *= i
	return re

H_count = getcnt(H)
W_count = getcnt(W)

ans = 1
if H_count % W_count == 0:
	if W_count == 2:
		ans = 2
	elif W_count > 2:
		W_list = getfac(W_count)
		for i in W_list:
			if i == 2:
				ans += 2
			else:
				ans += 1
elif H_count % W_count == 0:
	if H_count == 2:
		ans = 2
	elif H_count > 2:
		H_list = getfac(H_count)
		for i in H_list:
			if i == 2:
				ans += 2
			else:
				ans += 1

ans = (ans + (2**W_count + 2**H_count - 1)) % (10**9 + 7)
ans = ans ** int(H/H_count) % (10**9 + 7)
ans = ans ** int(W/W_count) % (10**9 + 7)
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = (pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W)) - 2) % MOD
print(pow(ans, ga*gb, MOD))

Submission status: Runtime Error

Solution code:
from math import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W)) - 2
print(pow(ans, ga*gb, MOD))

Submission status: Runtime Error

Solution code:



import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( 2 ** ( H // htgcd)) + 2 ** (W // wtgcd)) - 3)
p += 2 ** fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)

Submission status: Runtime Error

Solution code:
from math import gcd
mod = 10 ** 9 + 7
n, m, t = map(int, input().split())
a = gcd(n, t)
b = gcd(m, t)
n //= a
m //= b
ret = pow(2, n, mod) + pow(2, m, mod) + pow(2, gcd(n, m), mod) - 3
print(pow(ret, a * b, mod))