題面：

Miguel Angelo is a great sculptor, widely recognized for his outdoor sculptures. In his hometown, it is very common to find one of his creations in squares and gardens. People love his sculptures, not only for their beauty, but also because they look like new even after decades. The sculptures do not degrade easily due to the material and technique developed by Miguel and his staff over the years. To build the sculptures, he first constructs its base by stacking blocks of waterproof plaster (his secret material), forming several stacks of blocks in a straight line. He always uses identical blocks, and each stack has at least one block. To stabilize the structure, he surrounds it by two big glass panes, one behind the stacks and one in front of them. Then he waits for the rain for as long as it takes. If the structure is such that it doesn’t accumulate water during this procedure, Miguel is sure that the base can be used to obtain a piece of long-lasting artwork. Notice that water will accumulate on a block if there are obstacles (other blocks) on both sides (to the left and to the right). The following picture shows the front view of several different bases. All of them consist of three stacks made of a total of six blocks, with each stack having at least one block as required. However, the eight bases on the left will lead to long-lasting artwork, while the two bases on the right will not.

Miguel Angelo is receiving a lot of sculpture requests. Although he has all the freedom to create the artwork, he wants to be fair and use the same number of stacks and the same number blocks in each of the sculptures. Since he doesn’t want to sell identical sculptures to different clients, he will construct a different base each time. He worries that he won’t be able to fulfill all the requests. Help him calculate the number of different bases given the number of stacks and the number of blocks that the base must have.

Input

The input consists of a single line that contains two integers S and B (1 ≤ S ≤ B ≤ 5000) indicating respectively the number of stacks and the number of blocks that the base must have.

Output

Output a single line with an integer indicating the number of different bases that don’t accumulate water which Miguel can construct. Because this number can be very large, output the remainder of dividing it by 109 + 7.

Sample input

3 6

Sample output

8

Sample input

3 7

Sample output

12

題意：

大致就是給了 B 個積木，底部放置 S 個積木，求剩余積木在底座上擺放并且不產生凹槽擺放的組合數量，

思路：

在剛開始我排除了 dp （因為我真的太菜了，找不到狀態，以為只是容斥就能做的，ca），事后補題后發現是一個 dp 題，并且需要維護，

首先考慮定義狀態，這個狀態由于經過前綴和的維護，不是直接遞推出來的，所以比較難想象狀態，

仔細考慮一下，題目要求的是底座為 S ，上邊防止 S - B 個數量的積木并且不組成凹槽的擺放組合數量，其實整體無論擺了幾層，去掉最后一層，上邊仍舊滿足著不存在凹槽，所以上一層便是一個底座為 x（1 <= x <= S），上次 S - B -x 的數量的積木擺放不組成凹槽的個數，

所以可以設定為dp [ i ][ j ]的狀態為 最下層為 i ，上層擺放 j 個積木并且不組成凹槽的數量，由于每次底座上方的次層數量不固定，擺放方式也不固定，例如 S 的底座上方一個積木有 S個擺放方法，所以可以得到如下的 dp 轉移方程：

dp[ i ][ j ] = dp[ 1 ][ j - 1] * i + dp[ 2 ][ j - 2 ] * ( i - 1 ) + ··· + dp[ i ][ j - i ] * ( i - j ) ( j >= i )

dp[ i ][ j ] = dp[ 1 ][ j - 1] * i + dp[ 2 ][ j - 2 ] * ( i - 1 ) + ··· + dp[ j ][ 0 ] * ( i - j ) (j < i)

推出來轉移方程后，發現這是一個三維的回圈，再瞪眼看一下資料量，emmmm，鐵超時，于是可以每求出一個dp[ i ][ j ]之后，將其的數值加到累加和中去，通過每一輪前綴和，減少第三輪的回圈，從而得出兩重回圈的結果，

而累加和的存在，也需要我們建立一個合適的sum陣列，很顯然，每一次dp陣列所需的元素都具有一個相同的因素，那便是 i + j 的值相同，所以我們便可以根據這個值來設立前綴和陣列，即上方總共為（ i + j ）個積木的組成數量，因為后邊需要乘數，但是每個乘數也是與 i 緊緊相關聯的，于是每次經過一次 j 層的回圈，我們可以加上上次dp陣列提供的貢獻，便構成了一直滾動的前綴和，

由于每一輪dp陣列都會對不同的i + j提供貢獻，所以我們需要記錄所有的總貢獻數量，利用pre陣列定義為前邊總共 i + j 個積木的總貢獻，再加上sum陣列的貢獻，便是 j 個積木在底座 i 上的貢獻，

首先我們也需要考慮dp陣列以及sum陣列的初始化，很顯然，當j=0時，dp[ i ][ j ]的值顯然為1，此時sum陣列也應該不斷更新，

代碼：

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e3+5;
const int mod=1e9+7;
int sum[maxn*2],dp[maxn][maxn],pre[maxn*2];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int s,b;cin>>s>>b;
    b-=s;
    for(int i=1;i<=s;i++){
        for(int j=0;j<=b;j++){
            sum[j]=(sum[j]+pre[j])%mod;
            if(j==0)dp[i][j]=1;
            else {
                dp[i][j]=(dp[i][j]+sum[j])%mod;
            }
            pre[i+j]=(pre[i+j]+dp[i][j])%mod;
        }
    }
    cout<<dp[s][b]<<endl;
    return 0;
}
/*
3 6
3 7
*/

參考：Gym102428F Fabricating Sculptures {DP}【線性DP】（前綴和）_Hc_Soap的博客-CSDN博客qGym102428F Fabricating Sculptures（DP+前綴和）DescriptionMiguel Angelo is a great sculptor, widely recognized for his outdoor sculptures. In his hometown, it is very common to find one of his creations in squares and gardens. People love his sculptures, not ohttps://blog.csdn.net/Hc_Soap/article/details/108984133?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163206830216780255255835%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163206830216780255255835&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-3-108984133.first_rank_v2_pc_rank_v29&utm_term=F+-+Fabricating+Sculptures+Gym+-+102428F+&spm=1018.2226.3001.4187

侵刪，