SP5649 DTPOLY - Divide Polygon

本题的困难版本：[DTPOLY2](https://www.luogu.com.cn/problem/SP13953)。 我们现在来考虑一个包含 $N$ 个顶点的正多边形的切割方法。每一次，我们可以沿着某个多边形的一条弦（顶点与顶点的连线）进行切割，将这个多边形一分为二。假设每个顶点都是不同的。那么对于一个正方形（$4$ 个顶点的正多边形），我们一共有 $3$ 种方法切割它，沿两条对角线切割或者根本不切割。但是如果要将其切割成 $2$ 份则只有 $2$ 种方法；要将其切割成 $4$ 份是不可能的（注意每一次切割我们只对一个多边形操作，不能一次将 $2$ 个三角形切成 $4$ 个三角形）。 现在我们的问题就是，对于一个包含 $N$ 个顶点的正多边形，要把它切成 $K$ 份，有多少种切法？这个切法数目可能很多，只要求输出切法总数模 $10^9$ 的余数。你的任务就是编写程序解决这个问题。

输入包含一行两个正整数表示 $N$ 和 $K$。

输出包含一行一个整数表示答案模 $10^9$ 的余数。特别的，如果无法分出 $K$ 份，请输出 $-1$。

对于 $100\%$ 的数据，$3\le N\le100,1\le K\le100$。 翻译 @\_Sunmoon\_