using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long a = input[0];
        long b = input[1];
        long num = 1;
        int count = 0;
        int flag = 0;
        long M = 0;

        while (num < 10000001)
        {
            if (b-- == 0)
            {
                flag = 1;
                break;
            }
            num *= a;
            ++count;
        }

        if (flag == 1)
        {
            M = 10000000;
            Console.WriteLine(M);
            Console.WriteLine(num % M);
        }
        else
        {
            M = num - 1;
            var c = b % count;
            Console.WriteLine(M);
            Console.WriteLine(Math.Pow(a, c) % M);
        }
    }
}