Another Contest 7 Problem 4 - Team Assignments

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.5s
Memory limit: 256M

Problem types

Ren has recently created a website, Ternary Search, which he intends on turning into the premier platform for competitive programmers to talk about anything.

Ren's website has become quite popular, and now has N users. The friendship graph is quite strange though, the friendships form a structure where for any distinct two users a and b, there is a unique sequence of distinct users a, u_1, \dots, u_k, b such that adjacent users in the sequence are friends.

Ren wants to create a team programming contest where there are exactly K teams that compete. There are two constraints for teams - each team must contain at least one user (each user is on exactly one team), and if two users are on the same team, they cannot have been friends to begin with. Every user on the website will participate in this contest.

Let f(G) be the number of distinct arrangements of K teams that can be formed. The teams are labeled, so two arrangements of teams are considered distinct if there exists some user u that is on team t in one arrangement and not on team t in the other arrangement.

Compute the median value of f(G) over all possible friendship structures. Two friendship structures are different if there are two users u and v who are friends in one structure but not friends in the other.

For the purposes of this problem, we define the median to be any integer X such that at most half the integers in the collection are larger than X and at most half the integers in the collection are smaller than X. This definition may not match conventional definitions of median but is consistent with the formal definition of median. Note that this means that the median is not necessarily unique.


1 \le K \le 10^5

K \le N \le 10^{18}

Input Specification

The first and only line of input contains two space-separated integers, N and K.

Output Specification

Output the median modulo 998\,244\,353. Note that you should be computing the median first and then taking it modulo 998\,244\,353, as opposed to taking the modulo of all values and computing the median of that collection.

Any valid median that respects the above definition will be accepted.

Sample Input

3 2

Sample Output



There are no comments at the moment.