14851485 SUSTech Online Judge
Problem 1485 --Routes

1485: Routes

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

Description

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).

Input

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

Output a single integer indicating the answer.

Sample Input

0 0 2 3 59

Sample Output

10

HINT

Source

 

[Submit][Status]