def main():
    a, n = map(int, input().split())
    print(10**7)
    print(pow(a, n, 10**7))


if __name__ == '__main__':
    main()