You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this meeting because they have realized how much cooler the Android lock screen is, and they want to 1-UP them. Everyone in the room stares at you as Ghost Steve cries, "Help me, CodeGolf Man! You're my only hope!"
The Android lock screen is a 3 x 3 grid of dots that can be connected by swiping a finger from one dot to the next, creating a path. A password is considered any possible path that includes any number of dots, and excludes any number of dots. (On an actual phone, the path must be at least 4 dots long. For this challenge, ignore that restriction.) Apple plans to replace the 3 x 3 grid with an M x N grid, which is (M*N)/9 times better!
For example, on a 3x3 grid with dots numbered from 1 to 9:
1 2 3 4 5 6 7 8 9
Some valid paths are:
1 3 7,2,3 1,5,9,2 1,8,6,5,4 4,2,3,5,6,7,8,9 5,9,6,4
And some invalid paths are:
1,3 1,9,5 7,5,4,7 4,6
Your input will be three numbers:
Where the grid is M x N, and d is the length of the path
1 <= M <= 16 1 <= N <= 16 1 <= d <= M * N
Your program or function will be given the input as a comma separated string, and it must return the number of possible passwords of that length. For example:
Input: 2,2,1 Output: 4 Input: 2,2,2 Output: 12 Input: 7,4,1 Output: 28
Standard code golf rules apply, shortest code wins!
//If I've made a mistake or the rules are unclear, please correct me!