include

include

include

using namespace std;

typedef long long s64;

const int MaxD = 200000;

const int MaxTN = 524288; const int FFT_P = 1005060097; const int FFT_G = 5;

inline int modpow(int a, s64 n) { int t = a; int res = 1; for (s64 i = n; i > 0; i >>= 1) { if (i & 1) res = (s64)res * t % FFT_P; t = (s64)t * t % FFT_P; } return res; }

int fftG[MaxTN];

void fft(int n, int step, int *a, int *out) { if (n == 1) { out[0] = a[0]; return; }

int m = n >> 1;
fft(m, step + 1, a, out);
fft(m, step + 1, a + (1 << step), out + m);
for (int i = 0; i < m; i++)
{
    int e = out[i], o = (s64)out[i + m] * fftG[i << step] % FFT_P;
    out[i] = (e + o) % FFT_P;
    out[i + m] = (e + FFT_P - o) % FFT_P;
}

}

void polymul(int n, int *a, int *b, int *c) { int g = modpow(FFT_G, (FFT_P - 1) / n); fftG[0] = 1; for (int i = 1; i < n; i++) fftG[i] = (s64)fftG[i - 1] * g % FFT_P;

static int fa[MaxTN];
static int fb[MaxTN];

fft(n, 0, a, fa);
fft(n, 0, b, fb);

reverse(fftG + 1, fftG + n);

for (int i = 0; i < n; i++)
    fa[i] = (s64)fa[i] * fb[i] % FFT_P;

fft(n, 0, fa, c);

int revN = modpow(n, FFT_P - 2);
for (int i = 0; i < n; i++)
    c[i] = (s64)c[i] * revN % FFT_P;

/*
fill(c, c + n, 0);
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        c[(i + j) % n] = (c[(i + j) % n] + (s64)a[i] * b[j]) % FFT_P;*/

}

int calc(int n, int d) { static int fact[MaxD + 1]; fact[0] = 1; for (int x = 1; x <= d; x++) fact[x] = (s64)fact[x - 1] * x % FFT_P; static int rfact[MaxD + 1]; rfact[1] = 1; for (int x = 2; x <= d; x++) rfact[x] = (FFT_P - (s64)(FFT_P / x) * rfact[FFT_P % x] % FFT_P) % FFT_P; rfact[0] = 1; for (int x = 1; x <= d; x++) rfact[x] = (s64)rfact[x] * rfact[x - 1] % FFT_P;

static int a[MaxTN];
static int b[MaxTN];

int tn = 1;
while (tn < (d + 1) * 2)
    tn <<= 1;

fill(a, a + tn, 0);
fill(b, b + tn, 0);

for (int i = 0; i <= d; i++)
    a[i] = (s64)rfact[i] * modpow(i, d) % FFT_P;
for (int i = 0; i <= d; i++)
    b[i] = (s64)rfact[i] * modpow(FFT_P - 1, i) % FFT_P;

static int strl2[MaxTN];
polymul(tn, a, b, strl2);

/*
for (int i = 0; i <= d; i++)
{
    strl2[i] = 0;
    for (int j = 0; j <= i; j++)
    {
        int cur = (s64)rfact[j] * modpow(j, d) % FFT_P * rfact[i - j] % FFT_P * modpow(FFT_P - 1, i - j) % FFT_P;
        strl2[i] = (strl2[i] + cur) % FFT_P;
    }
}
*/

/*
strl2[0] = 1;
for (int i = 1; i <= d; i++)
{
    strl2[i] = 0;
    for (int j = i; j >= 1; j--)
        strl2[j] = ((s64)strl2[j] * j + strl2[j - 1]) % FFT_P;
    strl2[0] = 0;
}*/

int res = 0;
for (int k = 0, n_k = 1; k <= min(d, n); n_k = (s64)n_k * (n - k) % FFT_P, k++)
{
    int cur = (s64)strl2[k] * n_k % FFT_P * modpow(2, n - k) % FFT_P;
    res = (res + cur) % FFT_P;
}
return res;

}

int main() { int nT; cin >> nT; while (nT--) { int n, d; scanf("%d %d", &n, &d);

    n--;
    int res = (s64)(n + 1) * modpow(2, (s64)n * (n - 1) / 2) % FFT_P;
    res = (s64)res * calc(n, d) % FFT_P;
    printf("%d\n", res);
}

return 0;

}

So, funny story: I spent many hours over the last two days poring over identities involving binomial coefficients, in hopes of massaging a sum that took O(K^2) into a sum that takes O(K). I assumed that there had to be some kind of combinatorial trick involving Pascal's triangle, because otherwise how could this challenge be possible? Anyway, I finally found one, and everything passes.

Lo and behold, the editorial mentions the same formula that I ended up finding --- as an alternative solution (submitted by bayleef). The intended method of solution from the editorial did not occur to me even once, and I'm sure I wouldn't ever have considered it even if I spent another two weeks on this problem. :-) Perhaps if I were more familiar with particular large primes, I might have taken the "unusual" modulus as a hint, but it was totally lost on me. :-)

Anyway, kevinsogo mentions in the editorial that he couldn't see a proof that bayleef's formula gives the same answer as the naive (and slow) formula involving Stirling numbers; the comments in my submission outline the combinatorial argument that shows why the two formulas are equivalent.

Please feel free to drop me a line if I can offer any assistance with solving this challenge in an apparently completely unintended way. :-)

In the third test case, if n=3, how can there be 3 edges without a loop? am I missing something trivial?

can some one explain me what if n=4 and in case if there are three edges