/**
 * Main class of the Java program.
 *
 * For TESTING and SUBMITTING: Uncomment the @RunTests annotation
 * (Remove the two slashes at the beginning of line ~10)
 * 
 */
import java.util.Scanner;

@RunTests
public class Main {
    
    public static int partition(int amount, int[] billsAndCoins, int start) {
        
        if (amount == 0){
            return 1; 
        }
        
        else if (amount < 0){
            return 0;
        }
        
        else if (start >= billsAndCoins.length){
            return 0; 
        }
        
        else{
            int a = partition(amount, billsAndCoins, start+1);
            int b = partition(amount-billsAndCoins[start], billsAndCoins, start);
            return a + b;
        }
    }

    public static void main(String[] args) {
        int[] billsAndCoins = {1000, 200, 100, 50, 20, 10, 5, 2, 1};
        System.out.println("In how many ways can I own x CHF for x=?");
        Scanner input = new Scanner (System.in);
        int amount = input.nextInt();
        int ways = partition(amount, billsAndCoins, 0);
        System.out.println(ways);
    }

}