In the JAG country, there are a total of universities, and we plan to invite students to a training camp. Each student is affiliated with one of the universities. During the training camp, the students will be accommodated in twin rooms, meaning that each room will be assigned to exactly two students.
To promote diverse interactions among the students, our goal is to achieve a "good room assignment". A room assignment is considered good if and only if the students sharing the same room come from different universities.
Here, we are wondering how often a good room assignment is feasible. There are possible sequences of universities to which each student belongs, and please find for how many of them there is a good room assignment.
Actually, we don't yet know how many rooms we can provide. Therefore, for each of , please find for how many of the sequences of universities there is a good room assignment.
Since the answer may be huge, print the answers modulo .
输入格式
The input is a single line containing an integer between and , inclusive.
输出格式
Output lines. In the -th line, you should output the answer for .
