Sum of Product of Binomial Coefficients
Source: aizu

Sum of Product of Binomial Coefficients
Problem Statement

You are given integers $N$ and $K$. For a positive integer $k$, $f(k)$is defined as follows.

The sum of $\begin{pmatrix} N \\ a_1 \end{pmatrix} \times \begin{pmatrix} a_1\\ a_2 \end{pmatrix} \times ... \times \begin{pmatrix} a_{k-1}\\ a_k \end{pmatrix}$ for all integer sequences $(a_1, a_2, ..., a_k)$ that satisfy the condition $N \geq a_1 \geq a_2 \geq ... \geq a_k \geq 0$.

Answer the remainder of $\sum _{k=1}^K f(k)$ divided by 998244353.

For each input, solve $T$ test cases.

Note that $\begin{pmatrix} A \\ B \end{pmatrix}$ represents "the number of ways to select $B$ distinct items from $A$ items" (i.e., the binomial coefficient).

Input
$T$
$case_1$
$\vdots$
$case_T$


Each test case is given in the following format.

$N$ $K$


The input satisfies the following constraints.

All test cases consist of integers.
$1 \leq T \leq 10^5$
$0 \leq N \leq 10^9$
$1 \leq K \leq 2 \times 10^5$
The sum of $K$ in one test case does not exceed $2 \times 10^5$.
Output

Output the remainder of $\sum _{k=1}^K f(k)$ divided by 998244353 for each test case.

Sample Input
3
3 3
0 1
31415 92653

Sample Output
99
1
276482222


C++ solution:
// AOJ #3600 Sum of Product of Binomial Coefficients
// 2025.3.3

#include <iostream>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int Cin() {  // 整数の入力
    int n = 0, c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

void Cout(int n) { // 整数の表示（出力）
    char b[30];
    if (!n) pc('0');
    else {
        if (n < 0) pc('-'), n = -n;
        int i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
        while (i--) pc(b[i]);
    }
    pc('\n');
}

ll modexp(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while(b) {
        if(b & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return r;
}

int main(){
    int T = Cin();
    while(T--){
        ll N = Cin();
        int K = Cin();
        ll ans = 0;
        if(N == 0) ans = K;
        else {
            int i = 1;
            while (i <= K) ans = (ans + modexp(++i, N)) % MOD;
        }
        Cout(ans);
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const MOD = 998244353

func modexp(a, b int64) int64 {
	var res int64 = 1
	a %= MOD
	for b > 0 {
		if b&1 == 1 {
			res = (res * a) % MOD
		}
		a = (a * a) % MOD
		b >>= 1
	}
	return res
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())

	for t := 0; t < T; t++ {
		scanner.Scan()
		N, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		scanner.Scan()
		K, _ := strconv.Atoi(scanner.Text())

		var ans int64 = 0
		if N == 0 {
			ans = int64(K % MOD)
		} else {
			for k := 1; k <= K; k++ {
				term := modexp(int64(k+1), N)
				ans = (ans + term) % MOD
			}
		}
		fmt.Fprintln(writer, ans)
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;

    static long modexp(long a, long b) {
        long res = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long N = Long.parseLong(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            long ans = 0;
            if (N == 0) {
                ans = K % MOD;
            } else {
                for (int i = 2; i <= K + 1; i++) {
                    ans = (ans + modexp(i, N)) % MOD;
                }
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

JavaScript solution:
const readline = require('readline');

const MOD = 998244353n;

function modexp(a, b) {
    let res = 1n;
    a = BigInt(a) % MOD;
    b = BigInt(b);
    while (b > 0n) {
        if (b % 2n === 1n) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b = b >> 1n;
    }
    return res;
}

async function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    const input = [];
    for await (const line of rl) {
        input.push(line.trim());
    }

    const T = parseInt(input[0]);
    const results = [];
    
    for (let i = 1; i <= T; i++) {
        const [N, K] = input[i].split(' ').map(x => BigInt(x));
        let ans = 0n;
        
        if (N === 0n) {
            ans = K % MOD;
        } else {
            // Precompute powers for optimization
            const maxPower = K + 1n;
            const powers = new Map();
            for (let j = 2n; j <= maxPower; j++) {
                powers.set(j, modexp(j, N));
            }
            
            for (let j = 1n; j <= K; j++) {
                ans = (ans + powers.get(j + 1n)) % MOD;
            }
        }
        
        results.push(ans.toString());
    }
    
    console.log(results.join('\n'));
    rl.close();
}

main().catch(err => {
    console.error('Error:', err);
    process.exit(1);
});

Python solution:
import sys
MOD = 998244353

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    results = []
    for _ in range(T):
        N = int(input[ptr])
        K = int(input[ptr + 1])
        ptr += 2
        if N == 0:
            ans = K % MOD
        else:
            ans = 0
            for k in range(2, K + 2):
                ans = (ans + pow(k, N, MOD)) % MOD
        results.append(ans)
    print('\n'.join(map(str, results)))

solve()

Ruby solution:
require 'set'

MOD = 998244353

def modexp(a, b)
  result = 1
  a = a % MOD
  while b > 0
    if b.odd?
      result = (result * a) % MOD
    end
    a = (a * a) % MOD
    b >>= 1
  end
  result
end

def solve
  input = $stdin.read.split.map(&:to_i)
  ptr = 0
  t = input[ptr]
  ptr += 1
  results = []
  t.times do
    n = input[ptr]
    k = input[ptr + 1]
    ptr += 2
    if n == 0
      results << (k % MOD)
    else
      sum = 0
      (1..k).each do |i|
        term = modexp(i + 1, n)
        sum = (sum + term) % MOD
      end
      results << sum
    end
  end
  puts results.join("\n")
end

solve