No.148 Exam Proctor (3)
タグ : / 解いたユーザー数 28
作問者 :
LayCurse
Problem Statement
A certain teacher (who wishes to remain anonymous) came up with the following problem while proctoring a final exam, as the Setsubun festival was going on right nearby.
To prevent cheating, students may not sit in adjacent seats at the same desk.
For example, at a desk with $3$ chairs, if $2$ students sit there, the only allowed arrangement is to use the chairs at both ends, and if $1$ student sits there, any of the $3$ chairs may be used.
In a certain unusual room, there is only $1$ desk, which has $C$ chairs.
Write a program that computes the number of ways to arrange the students when $P$ students take the exam in this room, modulo ${\rm mod}\ 10^9+7$.
(Note that, unlike the number of chair arrangement patterns in Exam Proctor (2), the students are distinguishable (see the first case of the sample).)
Note: As long as the program's execution time does not exceed 1 second and it outputs the correct answer (and it is a program that yukicoder accepts), it will be considered correct. (Perhaps looking at the list of submissions will tell you something?)
Figure 1. ...They were already packing up (in front of Yoshida Shrine, February 4, 2015)
Input
The first line contains an integer $T$ representing the number of test cases.Each test case is given in the following format.
$C$ $P$
$1 \leq T \leq 30$
$1 \leq C \leq 10^{10000}$
$1 \leq P \leq 10^{10000}$
Output
For each test case, output the number of patterns of arranging the students, modulo ${\rm mod}\ 10^9+7$.
Sample
Sample 1
Input
3 3 2 1 196547891657825679231564789567843659723659763246578365879364576378658372657842658746758638746587236589762187456587168 123456789 1
Output
2 0 123456789
First test case: The 2 students have no choice but to sit at both ends, and there are 2 arrangements depending on which student sits at which end.
Second test case: Impossible!
Third test case: Please sit in whichever chair you like.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。