Polo the Penguin and Houses

题意翻译

### 原题意 有编号$1\sim n$的$n$个房间,其中$i$号房间上有一个数字$p_i\in [1,n]$.玩家在$i$号房间时,下一个房间要前往的房间是$p_i$.已知玩家从编号$1\sim k$的房间出发时,他能走到$1$号房间;从编号$(k+1)\sim n$的房间出发时,他不能走到$1$号房间;从$1$号房间出发时,他能经若干步返回$1$号房间.求有多少组$p_1,\cdots,p_n$满足上述条件,答案对$1\mathrm{e}9+7$取模. 第一行输入两个整数$n,k\ \ (1\leq n\leq 1000,1\leq k\leq \min\{8,n\})$. ### 简单题意 构造一个包含编号$1\sim n$个节点的有向图,其中$1\sim k$号节点都存在到达$1$号节点的路径,$(k+1)\sim n$号节点都不存在到达$1$号节点的路径,求方案数.

题目描述

Little penguin Polo loves his home village. The village has $ n $ houses, indexed by integers from 1 to $ n $ . Each house has a plaque containing an integer, the $ i $ -th house has a plaque containing integer $ p_{i} $ ( $ 1<=p_{i}<=n $ ). Little penguin Polo loves walking around this village. The walk looks like that. First he stands by a house number $ x $ . Then he goes to the house whose number is written on the plaque of house $ x $ (that is, to house $ p_{x} $ ), then he goes to the house whose number is written on the plaque of house $ p_{x} $ (that is, to house $ p_{px} $ ), and so on. We know that: 1. When the penguin starts walking from any house indexed from 1 to $ k $ , inclusive, he can walk to house number 1. 2. When the penguin starts walking from any house indexed from $ k+1 $ to $ n $ , inclusive, he definitely cannot walk to house number 1. 3. When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house. You need to find the number of ways you may write the numbers on the houses' plaques so as to fulfill the three above described conditions. Print the remainder after dividing this number by $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The single line contains two space-separated integers $ n $ and $ k $ ( $ 1<=n<=1000,1<=k<=min(8,n) $ ) — the number of the houses and the number $ k $ from the statement.

输出格式

In a single line print a single integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

5 2

输出样例 #1

54

输入样例 #2

7 4

输出样例 #2

1728