[51nod1101]换零钱

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
int dp[100002];
const int mod=1e9+7;
int main(){
    int n;
    scanf("%d",&n);
    dp[0]=1;
    for(int i=0;i<13;i++){
        for(int j=a[i];j<=n;j++){
            dp[j]+=dp[j-a[i]];
            dp[j]%=mod;
        }
    }
    cout<<dp[n]<<"\n";
    return 0;
}