def stirling_2nd(n, k):
    if n == 0 and k == 0:
        return 1
    elif n == 0 or k == 0:
        return 0
    else:
        return stirling_2nd(n - 1, k - 1) + k * stirling_2nd(n - 1, k)
 
def p0_st(n, k):
    return sum(stirling_2nd(n, i) for i in range(1, k + 1))
 
def p0_emp(n, k):
    from itertools import product
    assignments_set = set()
    for slot_assign in product(range(k), repeat=n):
        assignment = [list() for _ in range(k)]
        for ball, slot in enumerate(slot_assign):
            assignment[slot].append(ball)
        assignments_set.add(tuple(sorted(tuple(slot) for slot in assignment)))
    return len(assignments_set)
 
if __name__ == '__main__':
    for i in range(1, 6):
        for j in range(1, 6):
            assert p0_st(i, j) == p0_emp(i, j), (i, j)

ZGVmIHN0aXJsaW5nXzJuZChuLCBrKToKICAgIGlmIG4gPT0gMCBhbmQgayA9PSAwOgogICAgICAgIHJldHVybiAxCiAgICBlbGlmIG4gPT0gMCBvciBrID09IDA6CiAgICAgICAgcmV0dXJuIDAKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIHN0aXJsaW5nXzJuZChuIC0gMSwgayAtIDEpICsgayAqIHN0aXJsaW5nXzJuZChuIC0gMSwgaykKCmRlZiBwMF9zdChuLCBrKToKICAgIHJldHVybiBzdW0oc3RpcmxpbmdfMm5kKG4sIGkpIGZvciBpIGluIHJhbmdlKDEsIGsgKyAxKSkKCmRlZiBwMF9lbXAobiwgayk6CiAgICBmcm9tIGl0ZXJ0b29scyBpbXBvcnQgcHJvZHVjdAogICAgYXNzaWdubWVudHNfc2V0ID0gc2V0KCkKICAgIGZvciBzbG90X2Fzc2lnbiBpbiBwcm9kdWN0KHJhbmdlKGspLCByZXBlYXQ9bik6CiAgICAgICAgYXNzaWdubWVudCA9IFtsaXN0KCkgZm9yIF8gaW4gcmFuZ2UoayldCiAgICAgICAgZm9yIGJhbGwsIHNsb3QgaW4gZW51bWVyYXRlKHNsb3RfYXNzaWduKToKICAgICAgICAgICAgYXNzaWdubWVudFtzbG90XS5hcHBlbmQoYmFsbCkKICAgICAgICBhc3NpZ25tZW50c19zZXQuYWRkKHR1cGxlKHNvcnRlZCh0dXBsZShzbG90KSBmb3Igc2xvdCBpbiBhc3NpZ25tZW50KSkpCiAgICByZXR1cm4gbGVuKGFzc2lnbm1lbnRzX3NldCkKCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6CiAgICBmb3IgaSBpbiByYW5nZSgxLCA2KToKICAgICAgICBmb3IgaiBpbiByYW5nZSgxLCA2KToKICAgICAgICAgICAgYXNzZXJ0IHAwX3N0KGksIGopID09IHAwX2VtcChpLCBqKSwgKGksIGop