Реши на с++

Вот аккуратное решение.

Идея: нумеруем друзей $1..n$, фотографии — это векторы-столбцы $v_j\in\{0,1\}^n$ (пустая колонка запрещена). Требуется посчитать число последовательностей из $k$ столбцов, где все суммарные вхождения по строкам одинаковы: $\sum_j v_{ij}=r$ для всех $i$ (какое-то $0\le r\le k$).

Сделаем включение–исключение по «пустым» столбцам. Пусть из $k$ столбцов ровно $s$ фиксируем пустыми. Тогда остаётся $m=k-s$ столбцов без запрета на пустоту. Число матриц $n\times m$ с одинаковыми суммами строк равно

$$B(m)=\sum_{r=0}^{m}\binom{m}{r}^n,$$

потому что для данного $r$ строки независимы (каждая выбирает $r$ позиций из $m$).

Тогда ответ

$$\text{Ans}=\sum_{s=0}^{k}(-1)^s \binom{k}{s}\, B(k-s) =\sum_{s=0}^{k}(-1)^s \binom{k}{s}\sum_{r=0}^{k-s}\binom{k-s}{r}^n$$

по модулю $998244353$.

Остаётся посчитать биномиальные коэффициенты за $O(1)$ через факториалы, а суммы — за $O(k^2\log n)$.

---

Код (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    if (!(cin >> n >> k)) return 0;

    // factorials up to k
    vector<long long> fact(k + 1), invfact(k + 1);
    fact[0] = 1;
    for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i % MOD;
    invfact[k] = mod_pow(fact[k], MOD - 2);
    for (int i = k; i > 0; --i) invfact[i - 1] = invfact[i] * i % MOD;

    auto C = [&](int n_, int r_) -> long long {
        if (r_ < 0 || r_ > n_) return 0LL;
        return fact[n_] * invfact[r_] % MOD * invfact[n_ - r_] % MOD;
    };

    // Precompute B[m] = sum_{r=0}^m C(m,r)^n for m=0..k
    vector<long long> B(k + 1, 0);
    for (int m = 0; m <= k; ++m) {
        long long s = 0;
        for (int r = 0; r <= m; ++r) {
            long long comb = C(m, r);
            s += mod_pow(comb, n);
            if (s >= MOD) s -= MOD;
        }
        B[m] = s;
    }

    long long ans = 0;
    for (int s = 0; s <= k; ++s) {
        int m = k - s;
        long long term = C(k, s) * B[m] % MOD;
        if (s % 2 == 0) {
            ans += term;
        } else {
            ans -= term;
        }
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;

    cout << ans % MOD << '\n';
    return 0;
}

Сложность: $O(k^2\log n)$ по времени (для $k\le 3000$ нормально) и $O(k)$ по памяти.