Từ đây đến cuối bài ta sẽ gọi ~\%~ là phép chia lấy dư.

Subtask 2

~dp[0][i] = 0~ ~(0 < i < n)~

~dp[0][0] = 1~

~dp[i][sum] = dp[i-1][sum] + dp[i-1][(sum-i)\%n]~

Kết quả là ~dp[n\times k][0]~.

Độ phức tạp: ~O(n^2\times k)~.

Subtask 3

Ta thấy vì mọi ngày Naot đều uống trà sữa như nhau; nên có thể gọi ~c_i = dp[n][i]~, khi đó xét đa thức:

~P(x)=(c_0\times x^0+c_1\times x^1+....+c_{n-1}\times x^{n-1})^k~

Đáp án sẽ là ~\sum_{i=0}^{k-1} h_{i\times n}~ với ~h_j~ là hệ số của ~x^j~ trong ~P~. Theo đó ta có thể thực hiện nhân đa thức sử dụng chia để trị để tính ~P~; nhằm tối ưu hóa thuật toán, khi nhân hai đa thức, ta viết ~h_{i \% n}~ thay cho ~h_i~.

Độ phức tạp: ~O(n^2 \times logk)~

Subtask 4

Gọi ~A\left(x\right)=\left[\left(1+x^0\right)\left(1+x^1\right)\dots\left(1+x^{n-1}\right)\right]^k = a_0x^0+a_1x^1+a_2x^2+\dots+a_nx^n+\dots~

Dễ thấy rằng ~a_i~ là số subset con có tổng bằng ~i~. Bài toán yêu cầu ta tính tổng các ~a_i~ với ~i~ là bội của ~n~.

Gọi ~\zeta_n~ là nghiệm đơn vị nguyên thủy cấp ~n~ (primitive ~n~th root of unity). Ta xét biểu thức sau:

~\sum_{i=1}^nA(\zeta_n^i)=a_0\sum_{i=1}^n\zeta_n^{0\times i} + a_1\sum_{i=1}^n\zeta_n^{1\times i}+a_2\sum_{i=1}^n\zeta_n^{2\times i}+\dots+a_n\sum_{i=1}^n\zeta_n^{n\times i}+\dots~

~=a_0\sum_{i=1}^n1 + a_1\sum_{i=1}^n\zeta_n^{ i}+a_2\sum_{i=1}^n\zeta_n^{2i}+\dots+a_n\sum_{i=1}^n1+\dots~

~=n(a_0+a_n+a_{2n}+\dots)+a_{1+nj}\sum_{i=1}^{n}\zeta_n^i+a_{2+nj}\sum_{i=1}^{n}\zeta_n^{2i}+\dots+a_{(n-1)+nj}\sum_{i=1}^{n}\zeta_n^{(n-1)i}\,\,\,(j \text{ là số nguyên})~

~=n(a_0+a_n+a_{2n}+\dots) + 0 + 0 +\dots + 0~

Từ biểu thức này ta thấy kết quả chúng ta cần tìm là: ~\frac{1}{n}\sum_{i=1}^nA(\zeta_n^i)~

Từ đây ta chỉ cần tìm cách tính ~A(\zeta_n^i)~.

Dễ thấy ở trường hợp đơn giản nhất, ~A(\zeta_n^n)=A(1)=\left[\left(1+1^0\right)\left(1+1^1\right)\dots\left(1+1^{n-1}\right)\right]^k = 2^{nk}~

Ta có nhận xét ~\zeta_n^{i\times j}~ với ~i~ cố định và ~j~ chạy từ ~1~ đến ~n~ thì ~\zeta_n^{i\times j}~ sẽ phân bố đều vào nghiệm đơn vị cấp ~n/gcd(n, i)~ (Phần chứng minh để lại cho bạn đọc).

Từ tính chất trên ta có: ~A(\zeta_n^i)=\left[\prod_{j=1}^{n/gcd(n,i)}\left(1+\zeta_{n/gcd(n,i)}^{j}\right)\right]^{gcd(n,i)\times k}~

Xét: ~x^n-1=\prod_{i=1}^n(x-\zeta_n^i)~

~\Rightarrow (-1)^n-1=\prod_{i=1}^n(-1-\zeta_n^i)~

~\Rightarrow \prod_{i=1}^n(1+\zeta_n^i)=\frac{(-1)^n-1}{(-1)^n}=\begin{cases}2, & n \% 2 = 1 \\ 0, & n\%2=0\end{cases}=2\times (n\%2)~

Từ đó ta có thể suy ra: ~A(\zeta_n^i) = \left[2\times \left(\frac{n}{gcd(n,i)}\%2\right)\right]^{gcd(n,i)\times k}=2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)~

Dựa vào công thức kết quả ~\frac{1}{n}\sum_{i=1}^nA(\zeta_n^i)~ đã nêu ở trên, ta khai triển:

~ans = \frac{1}{n} \sum_{i=1}^{n} \left[2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)\right]~

Độ phức tạp: ~O(n)~.

Subtask 5

Theo trên: ~ans = \frac{1}{n} \sum_{i=1}^{n} \left[2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)\right] = \frac{1}{n} \sum_{d|n} \left[2^{d\times k} \times \left(\frac{n}{d}\%2\right)\times \varphi\left(\frac{n}{d}\right)\right]~

Như vậy; thay vì phải duyệt từ 1 tới ~n~, ta chỉ cần duyệt qua các ước của ~n~ và duy trì việc tính ~\varphi(n)~ nhanh.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) (int) ((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-12;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
int _mult(int x, int y) {return (long long) x * y % MOD;}
template<typename ...Y> int _mult(int x, Y... y) { return (long long) x * _mult(y...) % MOD; }
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
template<typename X> void debug(X x) { cerr << x << "] "; }
template<typename X, typename ...Y> void debug(X x, Y... y) { cerr << x << " "; debug(y...); }
#define db(...) cerr << "[" << #__VA_ARGS__ << ": ", debug(__VA_ARGS__);
#define endln cerr << "\n";
#define LIKELY(x)   (__builtin_expect(!!(x), 1))
#define UNLIKELY(x) (__builtin_expect(!!(x), 0))

template<typename num_t>
num_t mulmod(num_t a, num_t b, num_t p) {
  a %= p; b %= p;
  num_t q = (num_t) ((long double) a * b / p);
  num_t r = a * b - q * p;
  while (r < 0) r += p;
  while (r >= p) r -= p;
  return r;
}
template<typename num_t>
num_t powmod(num_t n, num_t k, num_t p) {
  num_t r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = mulmod(r, n, p);
    n = mulmod(n, n, p);
  }
  return r;
}

void chemthan() {
  const long long mod = 5600748293801LL;
  long long n, k; cin >> n >> k;
  vector<long long> prs;
  {
    long long t = n;
    for (int d = 2; (long long) d * d <= t; d++) if (t % d == 0) {
      while (t % d == 0) t /= d;
      prs.pb(d);
    }
    if (1 < t) prs.pb(t);
  }
  auto phi = [&] (long long d) {
    long long res = 1;
    for (auto pr : prs) {
      int cnt = 0;
      while (d % pr == 0) {
        if (cnt) {
          res = mulmod(res, pr, mod);
        }
        d /= pr, cnt++;
      }
      if (cnt) {
        res = mulmod(res, pr - 1, mod);
      }
    }
    return res;
  };
  long long res = 0;
  auto add = [&] (long long d) {
    long long t = mulmod(n / d, k, mod - 1);
    res += mulmod(powmod(2LL, t, mod), phi(d), mod);
    res %= mod;
  };
  for (int d = 1; (long long) d * d <= n; d++) if (n % d == 0) {
    if (d % 2 == 1) add(d);
    if (d < n / d && n / d % 2 == 1) add(n / d);
  }
  res = mulmod(res, powmod(n, mod - 2, mod), mod);
  cout << res << "\n";
}

int32_t main(int32_t argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  int test = 1;
  cin >> test;
  FOR(it, 1, test + 1) {
    chemthan();
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}