Problem C: Routes

Problem C: Routes

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1879  Solved: 295
[Submit][Status][Web Board]


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.

Sample Input

0 0 2 3 59

Sample Output