308425: CF1516E. Baby Ehab Plays with Permutations

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Baby Ehab Plays with Permutations

题意翻译

你有一个长度为 $n$ 的序列 $p$ 满足 $p_i=i$,你可以进行 $x$ 次操作,每次操作找到两个不同的 $i,j$ 并且交换 $p_i,p_j$,问最终有几个可能的序列。对于 $1 \le i \le k$ 中的每个 $i$,求出当 $i=x$ 时的答案。 $1 \le n \le 10^9,1\le k \le 200$。

题目描述

This time around, Baby Ehab will play with permutations. He has $ n $ cubes arranged in a row, with numbers from $ 1 $ to $ n $ written on them. He'll make exactly $ j $ operations. In each operation, he'll pick up $ 2 $ cubes and switch their positions. He's wondering: how many different sequences of cubes can I have at the end? Since Baby Ehab is a turbulent person, he doesn't know how many operations he'll make, so he wants the answer for every possible $ j $ between $ 1 $ and $ k $ .

输入输出格式

输入格式


The only line contains $ 2 $ integers $ n $ and $ k $ ( $ 2 \le n \le 10^9 $ , $ 1 \le k \le 200 $ ) — the number of cubes Baby Ehab has, and the parameter $ k $ from the statement.

输出格式


Print $ k $ space-separated integers. The $ i $ -th of them is the number of possible sequences you can end up with if you do exactly $ i $ operations. Since this number can be very large, print the remainder when it's divided by $ 10^9+7 $ .

输入输出样例

输入样例 #1

2 3

输出样例 #1

1 1 1

输入样例 #2

3 2

输出样例 #2

3 3

输入样例 #3

4 2

输出样例 #3

6 12

说明

In the second example, there are $ 3 $ sequences he can get after $ 1 $ swap, because there are $ 3 $ pairs of cubes he can swap. Also, there are $ 3 $ sequences he can get after $ 2 $ swaps: - $ [1,2,3] $ , - $ [3,1,2] $ , - $ [2,3,1] $ .

Input

题意翻译

你有一个长度为 $n$ 的序列 $p$ 满足 $p_i=i$,你可以进行 $x$ 次操作,每次操作找到两个不同的 $i,j$ 并且交换 $p_i,p_j$,问最终有几个可能的序列。对于 $1 \le i \le k$ 中的每个 $i$,求出当 $i=x$ 时的答案。 $1 \le n \le 10^9,1\le k \le 200$。

加入题单

上一题 下一题 算法标签: