/*

HDU 6063 - RXD and math [ 数学,规律 ]  |  2017 Multi-University Training Contest 3

题意：

	求 Σ μ(i)^2 * sqrt( n^k/i ) [ 1 <= i<= n^k ]

	n,k <= 1e18

分析：

	首先 μ(i) 为莫比乌斯函数，若 i 是完全平方数的倍数则 μ(i) = 0 ，否则 μ(i) = ±1

	所以只有不是完全平方数的倍数的数才会对答案产生贡献

	然后任何数都能表示为 x =  a^2*b，即仅为一个非完全平方数的b的平方倍数

	n^k/i 代表 n^k 中 i 的倍数的个数

	则 sqrt(n^k/i) 代表 i 的 平方倍数 的个数

	联系前面的 x =  a^2*b ，可推得相当于每个数都只算了一次

	故答案为 n^k

*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const LL MOD = 1e9+7;

LL PowMod(LL a, LL m)

{

    a %= MOD;

    LL ret = 1;

    while (m)

    {

        if (m&1) ret = ret*a%MOD;

        a = a*a % MOD;

        m >>= 1;

    }

    return ret%MOD;

}

int main()

{

    LL n, k;

    int tt = 0;

    while (~scanf("%lld%lld", &n, &k))

    {

        printf("Case #%d: %lld\n", ++tt, PowMod(n, k));

    }

}