#P10147. [2017备战wc]Arrangement

    ID: 9203 传统题 1000ms 512MiB 尝试: 10 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-计数 DP以值为状态插板法双射计数补集计数Pascal 递推滚动数组可行性剪枝

[2017备战wc]Arrangement

Arrangement

题目描述

为便于文字表达,将原题用两个人像表示的两种性质分别记为 性质 A 和 性质 B。

称长度为 ss 的序列 a1,…,asa_1,\ldots,a_s 具有性质 A,当且仅当

$$\forall i\in[1,s],\qquad\lvert a_i-a_{(i\bmod s)+1}\rvert=1.$$

也就是说,相邻元素以及首尾元素的差的绝对值都为 11。

称序列 b1,…,brb_1,\ldots,b_r 具有性质 B,当且仅当:

  1. b1≤b2≤⋯≤brb_1\le b_2\le\cdots\le b_r。
  2. 1≤r≤n1\le r\le n,且 1≤bi≤m1\le b_i\le m。
  3. 将 bb 的元素重排列,所得的不同线性序列中,具有性质 A 的序列数量不超过 kk。

给定 n,m,kn,m,k,求具有性质 B 的序列数,对 109+710^9+7 取模。

两个序列仅在每个位置的元素都相同时才视为相同;循环移位或反转后如果逐项不同,就分别计数。例如 (1,2)(1,2) 和 (2,1)(2,1) 是两个不同序列。单元素序列不具有性质 A,因此即使 k=0k=0,它们仍具有性质 B。

输入格式

输入一行三个整数 n,m,kn,m,k。

输出格式

输出一行一个整数,表示答案。

数据范围

  • 10%10\% 的数据满足 n,m≤10n,m\le10。
  • 另有 10%10\% 的数据满足 k=1k=1。
  • 另有 10%10\% 的数据满足 k=0k=0。
  • 30%30\% 的数据满足 n,m≤25n,m\le25。
  • 全部数据满足 1≤n,m≤1001\le n,m\le100,0≤k≤1000\le k\le100。

样例1

输入:

2 1 0

输出:

2

合法的非递减序列为 (1)(1)、(1,1)(1,1),两者均没有具有性质 A 的重排列。

样例2

输入:

2 2 2

输出:

5