from collections import Counter
from math import factorial
from fractions import gcd
 
def solution(w, h, s):
    # Your code here
    grid=0
    for cpw in partition_cycles(w):
        for cph in partition_cycles(h):            
            m=count_cycles(cpw, w)*count_cycles(cph, h)
            grid+=m*(s**sum([sum([gcd(i, j) for i in cpw]) for j in cph]))
 
    return grid//(factorial(w)*factorial(h))
 
def count_cycles(c, n):
    num_cycles = factorial(n)
    for a, b in Counter(c).items():
        num_cycles //= (a**b) * factorial(b)
    return num_cycles
 
def partition_cycles(n, i=1):
    yield [n]
    for i in range(i, n // 2 + 1):
        for p in partition_cycles(n - i, i):
            yield [i] + p
 
print(solution(2,3,4))

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgQ291bnRlcgpmcm9tIG1hdGggaW1wb3J0IGZhY3RvcmlhbApmcm9tIGZyYWN0aW9ucyBpbXBvcnQgZ2NkCgpkZWYgc29sdXRpb24odywgaCwgcyk6CiAgICAjIFlvdXIgY29kZSBoZXJlCiAgICBncmlkPTAKICAgIGZvciBjcHcgaW4gcGFydGl0aW9uX2N5Y2xlcyh3KToKICAgICAgICBmb3IgY3BoIGluIHBhcnRpdGlvbl9jeWNsZXMoaCk6ICAgICAgICAgICAgCiAgICAgICAgICAgIG09Y291bnRfY3ljbGVzKGNwdywgdykqY291bnRfY3ljbGVzKGNwaCwgaCkKICAgICAgICAgICAgZ3JpZCs9bSoocyoqc3VtKFtzdW0oW2djZChpLCBqKSBmb3IgaSBpbiBjcHddKSBmb3IgaiBpbiBjcGhdKSkKICAgICAgICAgICAgICAKICAgIHJldHVybiBncmlkLy8oZmFjdG9yaWFsKHcpKmZhY3RvcmlhbChoKSkKCmRlZiBjb3VudF9jeWNsZXMoYywgbik6CiAgICBudW1fY3ljbGVzID0gZmFjdG9yaWFsKG4pCiAgICBmb3IgYSwgYiBpbiBDb3VudGVyKGMpLml0ZW1zKCk6CiAgICAgICAgbnVtX2N5Y2xlcyAvLz0gKGEqKmIpICogZmFjdG9yaWFsKGIpCiAgICByZXR1cm4gbnVtX2N5Y2xlcwoKZGVmIHBhcnRpdGlvbl9jeWNsZXMobiwgaT0xKToKICAgIHlpZWxkIFtuXQogICAgZm9yIGkgaW4gcmFuZ2UoaSwgbiAvLyAyICsgMSk6CiAgICAgICAgZm9yIHAgaW4gcGFydGl0aW9uX2N5Y2xlcyhuIC0gaSwgaSk6CiAgICAgICAgICAgIHlpZWxkIFtpXSArIHAKICAgICAgICAgICAgCnByaW50KHNvbHV0aW9uKDIsMyw0KSk=