题目描述

Deni 想在第二天完成 $N$ 项活动，活动编号为 $1$ 到 $N$。她准备先安排一个执行顺序，因此会制定一个“计划”。

一个计划由若干个偏好关系组成，每个偏好关系是一个有序对 $(x,y)$（满足 $1 \le x,y \le N$ 且 $x \ne y$），表示她更希望活动 $x$ 在活动 $y$ 之前进行。

更形式化地说：

• 一个计划包含若干个有序对，也可以一个都没有；
• 不允许出现重复的有序对；
• 不允许出现 $(x,x)$ 这样的有序对。

注意，对于一个给定计划，如果存在一条由偏好关系连接出的路径从 $u$ 到 $v$，那么 Deni 也会认为“$u$ 应当在 $v$ 之前完成”。

例如，如果计划中有偏好关系：

• $(1,2)$
• $(2,3)$
• $(3,4)$
• $(2,5)$

那么 Deni 会偏好：

• $1$ 在 $2,3,4,5$ 之前；

但对于 $4$ 和 $5$ 谁应当更早完成，则她并没有偏好。

由于某些计划中可能存在冲突，因此不一定所有活动都能按照偏好顺序同时完成。Deni 会尽可能多地选出一些活动，并为这些活动安排一个顺序，使得这个顺序不违反计划诱导出的偏好关系。

也就是说，如果对某个计划，最多能选出 $t$ 个活动，则存在一个序列：

$$a_1,a_2,\dots,a_t$$

使得不存在 $j>i$ 且 Deni 偏好 $a_j$ 在 $a_i$ 之前完成。

现在 Deni 想知道：有多少种不同的计划，使得她最多恰好能完成 $K$ 项活动？

请你编写程序 plans，求这样的计划数量，并对 $12289$ 取模。

实现细节

你需要实现如下函数：

int count_plans(int N, int K)

• N：活动数量；
• K：在满足计划偏好的前提下，最多能安排完成的活动数。

该函数对每个测试点只会被调用一次，你需要返回答案对 $12289$ 取模后的结果。

输入格式（本地评测器）

• 第一行两个整数 $N,K$，表示活动数量，以及最多可完成的活动数。

输出格式（本地评测器）

• 输出一行一个整数，表示函数返回值。

样例 #1

输入

2 2

输出

3

说明

若把偏好关系看成有向边，则恰好有三种计划使得最多可以完成 $2$ 项活动：

• 没有任何偏好关系；
• 只有 $(1,2)$；
• 只有 $(2,1)$。

样例 #2

输入

3 1

输出

18

样例 #3

输入

4 3

输出

774

数据范围

• $1 \le N \le 650$；
• $1 \le K \le N$。

子任务

子任务	分值	需要通过的子任务	$N$	$K$	其他限制
0		-			样例
1	9	0	$\le 5$	$\le N$	-
2	12	-	$\le 25$	$=N$
3	18	2	$\le 300$
4	20	0-3		$\le N$
5	14	0-4	$\le 400$
6	10	0-5	$\le 475$
7	17	0-6	$\le 650$

只有当某个子任务以及其依赖的所有子任务全部通过时，才能获得该子任务的分数。