#X10G. [LSOT-4] 集合

[LSOT-4] 集合

题目描述

记全集为 UU

定义一个操作方案为对每个非空集合 SUS \subseteq U 选择 SS 中任意一个元素作为 SS 的代表元,记为 r(S)r(S)

一种操作方案是好的当且仅当对任意非空集合 SUS \subseteq U,满足对于任意将其划分为 mm 个非空子集的方案 A1,A2,,AmA_1, A_2, \ldots, A_m1im,r(Ai)=r(S)\exists 1 \le i \le m, r(A_i) = r(S)

U={1,2,,n}U=\{1, 2, \ldots, n\} 时的本质不同的好的操作方案数,将答案对 10000000871000000087 取模。

两个操作方案是本质不同的,当且仅当存在某个非空集合 SUS \subseteq U,使得 r(S)r(S) 在两个操作方案中不同。

输入格式

仅一行,两个正整数 n,mn, m

输出格式

仅一行,一个整数,表示方案数对 10000000871000000087 取模的结果。

样例

3 1
24

样例 1 解释

所有方案都是好的,所以答案为 13×23×3=241^3 \times 2^3 \times 3 = 24

3 2
6

样例 2 解释

66 种方案分别为:

r({1,2,3})=1r(\{1, 2, 3\}) = 1r({1,2})=1 r(\{1, 2\}) = 1r({1,3})=1 r(\{1, 3\}) = 1r({2,3})=2 r(\{2, 3\}) = 2r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

r({1,2,3})=1r(\{1, 2, 3\}) = 1r({1,2})=1 r(\{1, 2\}) = 1r({1,3})=1 r(\{1, 3\}) = 1r({2,3})=3 r(\{2, 3\}) = 3r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

r({1,2,3})=2r(\{1, 2, 3\}) = 2r({1,2})=2 r(\{1, 2\}) = 2r({1,3})=1 r(\{1, 3\}) = 1r({2,3})=2 r(\{2, 3\}) = 2r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

r({1,2,3})=2r(\{1, 2, 3\}) = 2r({1,2})=2 r(\{1, 2\}) = 2r({1,3})=3 r(\{1, 3\}) = 3r({2,3})=2 r(\{2, 3\}) = 2r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

r({1,2,3})=3r(\{1, 2, 3\}) = 3r({1,2})=1 r(\{1, 2\}) = 1r({1,3})=3 r(\{1, 3\}) = 3r({2,3})=3 r(\{2, 3\}) = 3r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

r({1,2,3})=3r(\{1, 2, 3\}) = 3r({1,2})=2 r(\{1, 2\}) = 2r({1,3})=3 r(\{1, 3\}) = 3r({2,3})=3 r(\{2, 3\}) = 3r({1})=1 r(\{1\}) = 1r({2})=2 r(\{2\}) = 2r({3})=3 r(\{3\}) = 3

4 3
2592
114514 3
750017326
114514 19198
274658403

数据范围

本题采用捆绑测试。

  • 子任务 1(5 分):m=2m = 2
  • 子任务 2(6 分):n4n \le 4
  • 子任务 3(10 分):n3×103n \le 3 \times 10^3
  • 子任务 4(18 分):m=1m = 1
  • 子任务 5(26 分):m3×103m \le 3 \times 10^3
  • 子任务 6(35 分):无特殊限制。

对于全部的数据,1m<n2×1051 \le m < n \le 2 \times 10^5