题目描述
记全集为 U。
定义一个操作方案为对每个非空集合 S⊆U 选择 S 中任意一个元素作为 S 的代表元,记为 r(S)。
一种操作方案是好的当且仅当对任意非空集合 S⊆U,满足对于任意将其划分为 m 个非空子集的方案 A1,A2,…,Am,∃1≤i≤m,r(Ai)=r(S)。
求 U={1,2,…,n} 时的本质不同的好的操作方案数,将答案对 1000000087 取模。
两个操作方案是本质不同的,当且仅当存在某个非空集合 S⊆U,使得 r(S) 在两个操作方案中不同。
输入格式
仅一行,两个正整数 n,m。
输出格式
仅一行,一个整数,表示方案数对 1000000087 取模的结果。
样例
3 1
24
样例 1 解释
所有方案都是好的,所以答案为 13×23×3=24。
3 2
6
样例 2 解释
6 种方案分别为:
r({1,2,3})=1,r({1,2})=1,r({1,3})=1,r({2,3})=2,r({1})=1,r({2})=2,r({3})=3;
r({1,2,3})=1,r({1,2})=1,r({1,3})=1,r({2,3})=3,r({1})=1,r({2})=2,r({3})=3;
r({1,2,3})=2,r({1,2})=2,r({1,3})=1,r({2,3})=2,r({1})=1,r({2})=2,r({3})=3;
r({1,2,3})=2,r({1,2})=2,r({1,3})=3,r({2,3})=2,r({1})=1,r({2})=2,r({3})=3;
r({1,2,3})=3,r({1,2})=1,r({1,3})=3,r({2,3})=3,r({1})=1,r({2})=2,r({3})=3;
r({1,2,3})=3,r({1,2})=2,r({1,3})=3,r({2,3})=3,r({1})=1,r({2})=2,r({3})=3。
4 3
2592
114514 3
750017326
114514 19198
274658403
数据范围
本题采用捆绑测试。
- 子任务 1(5 分):m=2。
- 子任务 2(6 分):n≤4。
- 子任务 3(10 分):n≤3×103。
- 子任务 4(18 分):m=1。
- 子任务 5(26 分):m≤3×103。
- 子任务 6(35 分):无特殊限制。
对于全部的数据,1≤m<n≤2×105。