Hãy tính số lượng tập con có ~k~ phần tử của ~\{1, 2, ..., n\}~. Do con số này quá lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho ~m~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T\le 100~) - số lượng bộ dữ liệu.
• ~T~ dòng tiếp theo, mỗi dòng chứa ba số ~n, k, m~ (~1\le n \le 10^5; 0\le k\le n~, ~2\le m \le 10^9~).

Output:

• In ra ~T~ dòng tương ứng với kết quả các bộ dữ liệu (theo thứ tự trong input).

Sample Input 1

5
11 11 100
14 10 1000
14 4 10000
13 0 100000
12 11 1000000

Sample Output 1

1
1
1001
1
12