def main():
    a, n = map(int, input().split())
    m = 10000000
    print(m)
    print(pow(a, n, m))


if __name__ == '__main__':
    main()