GRID - Grid

Your task in this problem is very straightforward. You are given a point in the cartesian plane (m, n) where m > 0 and n > 0. You start at (0, 0) and are allowed to make unit moves along the positive x-axis or the positive y-axis. In other word if you are at a point (x, y) you can move to either (x+1,y) or (x,y+1). Your task is to find out the total number of ways you can reach (m, n) from (0, 0) modulus K.

Input

First line contains 'T', the number of testcases. The next 'T' lines contain three space separated integers m, n, K 1 <= m, n <= 1,000 K<=1,000,000

Output

A single integer denoting the total number of paths mod K.

Example

Input: 
1
4 4 100
 
Output: 
70

Added by:.:: Pratik ::.
Date:2010-01-13
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:algoCrack Elim-I

hide comments
2023-02-25 14:50:54
0.1 seconds is only suitable for limited languages. Some questions like this are very simple in C language. And for higher level languages, they are considered a difficult question.

It's just a little harder with high-level languages.

Last edit: 2023-02-25 15:23:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.