Ways to make a payment

Problem

A shop accepts coins of several values. Count the ways to pay an exact amount. Two ways are the same if they use the same coins in any order. Use a cached recursion.

Input, output and limits

Input: Line 1: the amount. Line 2: the coin values separated by spaces.
Output: One integer: the number of ways.
Constraints: 0 ≤ amount ≤ 500
1 to 6 different coin values, each from 1 to 500

Examples

Example

Input

11
1 5 10

Output

10+1, 5+5+1, 5+1x6 and 1x11 make 4 ways.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Decide coin by coin: use the current coin again, or move to the next coin.

Hint 2

Exactly 0 left is one way. Negative, or no coins left, is zero.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Routes around blocked cellshard
Longest common subsequencehard
Count inversionshard
Last person standinghard
Binomial coefficientmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Recursion in Depth problems

Problem

Input, output and limits

Examples

Hints

More Recursion in Depth problems