Partitioning a Hypersphere with Hyperplanes

ID: 18620

Type: Default

1000ms

256MiB

Given an n-dimensional hypersphere, you are provided with k hyperplanes (each of dimension n-1). These hyperplanes divide the hypersphere into several n-dimensional regions.

Your task is to compute the maximum number of regions the hypersphere can be partitioned into using these hyperplanes. The answer should be given modulo 998244353.

The maximum number of regions is given by the formula:

R(n,k) = \sum_{i=0}^{\min(n,k)} \binom{k}{i}

where \(\binom{k}{i}\) represents the binomial coefficient.

inputFormat

The input consists of a single line containing two integers n and k separated by a space, where n is the dimension of the hypersphere and k is the number of hyperplanes.

outputFormat

Output a single integer, which is the number of regions the hypersphere is divided into, taken modulo 998244353.

sample

2 1

#P5388. Partitioning a Hypersphere with Hyperplanes

Partitioning a Hypersphere with Hyperplanes