Problem 1485 --Routes
1485: RoutesTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 1874 Solved: 294
Paul is currently at (x1,y1) on a 2D plane. He wants to go to (x2,y2). He can move one unit upward or rightward at each step. Please print the number of different routes Paul can choose (since the result may be quite large, please module it by a given number M).
The first line contains five integers \(x1, y1, x2, y2, M. (x1\leq x2, y1\leq y2, |x1|,|y1|,|x2|,|y2|\leq 500, 2 \leq M \leq 10^9)\).
Output a single integer indicating the answer.
0 0 2 3 59