|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||138||48||42||44.211%|
In International Computer Products Company (ICPC), there is frequently a need to pass an important message from the employer to all the employees. The task of passing a message from ICPC employer to all the employees is accomplished by a series of calls over the telephone along organizational reporting lines. Kim, the employer of ICPC, plans to renovate the massage passing system so that an employee cannot make calls to other employees more than d times. For that purpose, Kim wants to know the number of telephone calls that are made at time t after he started the message passing subject to the constraints that:
Kim makes a call to an employee only when he starts the message passing. For example, the case when d = 2 is shown in the following table.
|Time t||Telephone calls||Number of calls at time t|
|0||Kim starts a message passing by making a call to A.||1|
|1||A makes a call to B (to pass the message).||1|
|2||A makes a call to C. B makes a call to D.||2|
|3||B, C, and D make calls to E, F, and G, respectively.||3|
In this example, Kim starts the message passing by making a call to A at time 0. The call takes one unit of time. At time 1, A is the only employee who has the message, and A makes a call to an uninformed employee B. At time 2, both A and B have the message; A and B make calls to uninformed employees C and D, respectively. Note that each employee cannot make calls to other employees more than two times in this case. As in the above table, three telephone calls are made at time 3.
Given d and t, you are to write a program to compute the number of telephone calls that are made at time t after Kim started the message passing.
Your program is to read from standard input. The input contains two integers, d and t (2 ≤ d ≤ 50, 1 ≤ t ≤ 2,000,000,000), where d represents the number of employees to which an employee can make calls, and t represents the time that has been passed since the massage passing started.
Your program is to write to standard output. Print exactly one line as follows: If m is the number of telephone calls that are made at the given time, print m mod 31,991. For example, if m = 32,000, the output should be 9.