You are picking up your friend from the airport, and you just got a call - your friend's flight was delayed! You know exactly how long it will be in minutes before your friend will be ready to get picked up, and you want to drive around until that point in time, arriving at the airport at exactly that time. You want to find out how many ways there are to reach the airport in exactly that amount of time.
The city layout is given as a String adj. The ith character of the jth element of adj is '.' if there is no road connecting intersection i to intersection j (both zero-indexed). If there is a road from intersection i to intersection j, the number of minutes it takes to travel that road is given as a number from '1' to '5'. Roads are not necessarily two-way, and two-way roads may not be the same speed both ways. You are at intersection start when you get your friend's call, and the airport is at intersection finish. Calculate the number of ways to get from intersection start to intersection finish in exactly time minutes. Since this number might be rather large, return the answer modulo 1000003.