Question: Q:I need to pay somebody 49 'fake-currency'. I have coins of denomination 1,2,3,4 and 5 and I can pay the amount with a maximum total of 15 coins. Let there be **M** ways of paying. Find the last 3 digits of M.

---

So I wrote a solution in javascript:  

```
function pay() {
var waysOfPaying= 0;
for (e = 0; e < 10; e++) {
    for (d = 0; d < 13; d++) {
        for (c = 0; c < 16; c++) {
            for (b = 0; b < 16; b++) {
                for (a = 0; a < 16; a++) {
                    if ((a + b + c + d + e <= 15) && (a + (2 * b) + (3 * c) + (4 * d) + (5 * e) == 49)) {
                        waysOfPaying++;
                        }
                    }
                }
            }
        }
    }
    return waysOfPaying % 1000 ;
}

```

The answer my code gives is 333 however the correct answer is 714. What did I do wrong?

Answer: 
Your algorithm is oriented towards the value of each coin. The problem is that it lost the importance of order: It finds that 9 coins with a value of 5, plus 1 coin with a value of 4 adds up to 49. But it misses the fact that 8 coins with a value of 5, followed by 1 with a value of 4, followed by another 5 also adds up to 49.

The original problem is based on moving from space to space, building a trail of moves to square 50. Focus on where you are, instead of the jump value. Think of the decision to be made on each space:
 - Are you on space 50? if so, you found a valid trail, count it.
 - Are you past square 49, or have you taken 15 moves to get here? If yes, this trail is ended, and there is no point jumping any further.
 - If no, then you can make 5 possible moves: jump 1, 2, 3, 4 or 5 spaces. After each one, evaluate your position again.

Hint: use a recursive function to simulate your actions on a space.
This question was also posted in cs.stackexchange.
I add a copy of my answer from there:

<https://cs.stackexchange.com/questions/19304/calculating-number-of-ways-of-paying-with-coins/19305?noredirect=1#comment38911_19305>

I would solve it with dynamic programming. Anyway, your code looks fine to me. You go over all the options, and count the ones who satisfy the conditions.

I ran your script and I saw that the number of options is exactly 333. If this is really the answer, so why in the question you were asked to give tthe last three digits?

I think, that maybe you need to count the options and consider the inner order.

For example: 5,5,5,5,5,5,5,5,5,4 will be count as an option, and 4,5,5,5,5,5,5,5,5,5 will be count as another option.

In this case the number of option will be much higher, and it make sense to ask for the last three digits.

You can change your code to this version of the question easily, by counting the number of permutation (notice that there are identical elements) for each tuple (a,b,c,d,e) that satisfies your conditions. It will be much more efficient than going over all the options.