CF288B Polo the Penguin and Houses

小企鹅 Polo 非常热爱自己的家乡村庄。村庄里有 $n$ 座房屋，编号为 $1$ 到 $n$。每座房屋门牌上都有一个整数，第 $i$ 座房屋的门牌上写着整数 $p_{i}$，其中 $1 \leq p_{i} \leq n$。 小企鹅 Polo 喜欢在村子里散步。散步方式如下：首先他站在编号为 $x$ 的房屋旁，然后他前往写在第 $x$ 号房屋门牌上的房屋（即前往 $p_{x}$ 号房屋），接着他去写在 $p_{x}$ 号房屋门牌上的房屋（即 $p_{p_{x}}$ 号房屋），如此往复。 已知以下条件： 1. 当小企鹅从编号为 $1$ 到 $k$ 的任意房屋开始散步时，他都能走到 $1$ 号房屋。 2. 当小企鹅从编号 $k+1$ 到 $n$ 的任意房屋开始散步时，他一定无法走到 $1$ 号房屋。 3. 当小企鹅从 $1$ 号房屋开始散步时，经过若干次非零步后，他可以回到 $1$ 号房屋。 请你计算有多少种方法可以在所有房屋门牌上填写数字，使上述三个条件都成立。请输出该数量对 $1000000007$ 取模的结果。

一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 1000, 1 \leq k \leq \min(8,n)$）——房屋总数和题目中的 $k$ 值。

输出一个整数，表示满足条件的方法数，对 $1000000007$ 取模。

由 ChatGPT 5 翻译