CF2119D Token Removing

[r-906 & Hatsune Miku - All I Can See Is You](https://www.youtube.com/watch?v=xv7hJ32xK94) Define a sequence of integers $ a $ valid if and only if $ \forall 1 \le i \le n, 0 \le a_i \le i $ . Define the weight $ f(a) $ of a valid sequence $ a $ of length $ n $ : - Initially, a token is placed at each integer point in the closed segment $ [1, n] $ on the number axis. - Perform $ n $ operations in sequence. During the $ i $ -th operation, if $ a_i \ne 0 $ , remove a token in the closed segment $ [a_i, i] $ that has not been removed; otherwise, do nothing. - $ f(a) $ is the number of ways to remove tokens. Two ways are considered different if there exists a $ t $ such that the positions of the tokens removed by the two ways are different at the $ t $ -th operation. For example, $ f([0, 2, 1]) = 2 $ , because we can remove tokens on $ 2, 1 $ or $ 2, 3 $ in sequence. JT gives you two integers $ n, m $ and asks you to find the sum of the weights over all $ (n + 1)! $ valid sequences of length $ n $ . Since the answer may be too large, print it modulo $ m $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows. The only line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5000, 10^8 \le m \le 1.01 \cdot 10^9 $ ) — the length of valid sequences, and the modulus. It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 2.5 \cdot 10^7 $ .

For each test case, output an integer — the sum of the weights over all $ (n + 1)! $ valid sequences of length $ n $ , modulo $ m $ .

In the first test case, valid sequences are $ [0] $ and $ [1] $ , and the answer is $ f([0]) + f([1]) = 1 + 1 = 2 $ . In the second test case, valid sequences are $ [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2] $ . The weight of $ [0, 1] $ is $ 2 $ , and the others are $ 1 $ , so the answer is $ 5 \cdot 1 + 1 \cdot 2 = 7 $ .