题目来源：BZOJ4402 Claris的剑，后被选入【2020六校联考NOIP 第1场】，题为【山水画】，搬题人memset0。
算法：组合计数。
“本质不同”这个要求比较毒瘤，我们必须先把它解决，以免重复计数。
发现每个数列，通过重新排列，一定能转化为如下两种形式之一：
- (1,(2,1),(2,1),dots,2,(3,2),(3,2),dots,3,(4,3),(4,3),dots,j)。
- (1,(2,1),(2,1),dots,2,(3,2),(3,2),dots,3,(4,3),(4,3),dots,j,j-1)。
其中(j)是序列里最大的数。
至于为什么所有数列一定能转化成这样，你只需要在知道每种值的出现次数以后，让字典序尽可能小，就一定会排成这个形式。
通过我打的括号，大家不难看出，如果把每种值第一次出现的位置拎出来，它们一定是一个恰为(1,2,dots ,j)的子序列（也就是序列里没有括号的部分）。而其它的位置，就是在这个子序列中，插入了若干个二元组。如果知道了序列长度(i)和最大元素(j)，则这样的序列数量，就相当于把(lfloorfrac{i-j}{2} floor)个元素，放入(j-1)个本质不同的盒子，盒子可以为空，方案数是({lfloorfrac{i-j}{2} floor+j-1-1choose j-1-1})。
注：把(x)个本质相同的物品放入(y)个本质不同的盒子，盒子可以为空。这个方案数可以用插板法求出。先在每个盒子里补一个物品，让所有盒子都不为空。然后插板，方案数是：({x+y-1choose y-1})。
于是可以得到一个复杂度(O(nm))的做法：枚举(i,j)，则答案是：
其中最前面的(1)，就是只有一个元素的序列({1})，为了避免组合数中出现负数，我们将其单独计算。
发现这个式子里，(i,j)纠缠在一起，很难直接计算。考虑枚举(k=lfloorfrac{i-j}{2} floor)的值。则答案又可以写成：
注：最后一步，是用到了(sum_{i=x}^{y}{ichoose x}={y+1choose x+1})。可以用杨辉三角形来理解：相当于求杨辉三角上连续若干行，每行的第(x)个数的和（画出来是一条斜向左下的斜线）。从上到下把每两个数合并为下一行的第(x+1)个数即可。也可以用组合意义来理解：从(y+1)个数里选(x+1)个数，枚举最后一个数在哪，然后在前面随便选。
通过预处理阶乘和逆元，求组合数是(O(1))的，因此最后的时间复杂度为(O(m))（(n,m)同阶）。
参考代码：
//problem:BZOJ4402
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=2e6;
const int MOD=1e9+7;
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int& x,int y){x=mod1(x+y);}
inline void sub(int& x,int y){x=mod2(x-y);}
inline int pow_mod(int x,int i){int y=1;while(i){if(i&1)y=(ll)y*x%MOD;x=(ll)x*x%MOD;i>>=1;}return y;}
int fac[MAXN+5],ifac[MAXN+5];
inline int comb(int n,int k){
if(n<k)return 0;
return (ll)fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
void facinit(int lim=MAXN){
fac[0]=1;
for(int i=1;i<=lim;++i)fac[i]=(ll)fac[i-1]*i%MOD;
ifac[lim]=pow_mod(fac[lim],MOD-2);
for(int i=lim-1;i>=0;--i)ifac[i]=(ll)ifac[i+1]*(i+1)%MOD;
}
int main() {
facinit();
int n,m;
cin>>n>>m;
int ans=1;
/*
for(int i=1;i<=n;++i){
for(int j=2;j<=m && j<=i;++j){
add(ans, comb((i-j)/2+j-1-1, j-1-1)); // (i-j)/2个东西,放进j-1个盒子,可以为空
}
}
*/
for(int j=0;j<=min(m-2,n-2);++j){
add(ans, comb((n-j-2)/2+j+1, j+1));
}
for(int j=0;j<=min(m-2,n-3);++j){
add(ans, comb((n-j-3)/2+j+1, j+1));
}
cout<<ans<<endl;
return 0;
}