English

It is easy to see that the solution of the problem will be 1 for 1 card and 1 1 for 2 cards because if there can be only one pack every card will be in that pack and if there are 2 packs each of the 2 cards must be in one of the packs so there is 1 combination for all these cases.

After this point we will have to find the relation for adding 1 more card to a combination. For example if we have a surprise pack combination with 3 packs and 4 cards {(1),(2,4),(3)} we can either add the 5th card to one of these three packs or create a new pack with it:

• {(1,5),(2,4),(3)} 3 packs
• {(1),(2,4,5),(3)} 3 packs
• {(1),(2,4),(3,5)} 3 packs
• {(1),(2,4),(3),(5)} 4 packs

Which means that for every combination with K packs, you will gain K different combinations for K packs and 1 combination for K+1 packs, by adding one more card.

Which also suggests that(for N being card count K being pack count)

Combination(N+1,K)=K\(\times\)Combination(N,K)+Combination(N,K-1).

• Because every combination that has K number of packs can generate K combinations that has K packs.
• and every combination that has K-1 number of packs can generate 1 combination that has K packs.

Turkish

Problemin çözümünün 1 kart için 1 ve 2 kart için 1 1 olacağını görmek kolaydır; çünkü eğer sadece bir paket bulunuyorsa her kart o pakette olacaktır, eğer 2 paket varsa o 2 pakete de birer kart girmesi gerektiğinden ve paketlerin sıralaması önemsiz olduğundan yine tek bir olasılık vardır. Bu nedenle tüm bu durumlar için 1 kombinasyon vardır.

Bu noktadan sonra kombinasyonumuza 1 kart daha eklemenin ilişkisini bulmamız gerekecek. Örneğin 3 pack ve 4 karttan oluşan bir sürpriz paket kombinasyonumuz varsa (örneğin: {(1),(2,4),(3)}) 5. ​​kartı bu üç paketten birine ekleyebilir veya onunla yeni bir paket oluşturabiliriz:

• {(1.5),(2,4),(3)} 3 paket
• {(1),(2,4,5),(3)} 3 paket
• {(1),(2,4),(3,5)} 3 paket
• {(1),(2,4),(3),(5)} 4 paket

Bu durumda; K paket içeren herhangi bir kombinasyona 1 adet kart eklersek, K paket içeren K farklı kombinasyon ve K+1 paket içeren 1 kombinasyon elde ederiz.

Bu da şunu gösterir (N, kart sayısı; K da paket sayısı olmak üzere):

Combination(N+1,K)=K\(\times\)Combination(N,K)+Combination(N,K-1).

• Çünkü K paket sayısına sahip her kombinasyon, K paket içeren K kombinasyon üretebilir.
• ve K-1 paket sayısına sahip her kombinasyon, K paket içeren 1 kombinasyon oluşturabilir.

Code

#include <bits/stdc++.h>
using namespace std;

#define min(a,b) (a<b?a:b)
const long long MODDD=1000000007;

int main(){
    int n;
    cin>>n;
    long long arr[n+1];
    arr[1]=1;

    if(n<=1){
        cout<<1<<endl;
        return 0;
    }

    for(int i=2;i<=n;i++){
        arr[i]=0;
        for(int k=i;k>=2;k--){
            arr[k]=(arr[k]*k+arr[k-1])%MODDD;
        }
    }

    long long res=0;
    for(int i=1;i<=n;i++){
        res=(res+arr[i])%MODDD;
    }
    cout<<res<<endl;
}