Another Contest 7 Problem 4 - Team Assignments

View as PDF

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 users. The friendship graph is quite strange though, the friendships form a structure where for any distinct two users and , there is a unique sequence of distinct users such that adjacent users in the sequence are friends.

Ren wants to create a team programming contest where there are exactly 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 be the number of distinct arrangements of teams that can be formed. The teams are labeled, so two arrangements of teams are considered distinct if there exists some user that is on team in one arrangement and not on team in the other arrangement.

Compute the median value of over all possible friendship structures. Two friendship structures are different if there are two users and 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 such that at most half the integers in the collection are larger than and at most half the integers in the collection are smaller than . 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.

Input Specification

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

Output Specification

Output the median modulo . Note that you should be computing the median first and then taking it modulo , 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

2