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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)
		)

Solution (Python):
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)

Solution (Python):
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  
        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))

Solution (Python):
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  
        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))

Solution (Python):
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  
        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))

Solution (Python):
from fractions import gcd
mod=10**9+7
def pow_r(x, n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow_r(x ** 2%mod, n // 2)%mod
    else:  
        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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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()
    
    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
    
    
    ans = pow(ans, gcd(h, t) * gcd(w, t), md)
    print(ans)

main()

Solution (Python):
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()
    
    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
    
    
    ans = pow(ans, gcd(h, t) * gcd(w, t), md)
    print(ans)

main()

Solution (Python):



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)



ans = pow( p , n , mod )

print (ans)

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):

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


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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)