CF2262E Paired Bracket Sequences

Farmer John is interested in bracket sequences with common pairings. A balanced bracket sequence is one in which every opening bracket is matched with a later closing bracket, and no prefix contains more closing brackets than opening brackets. For a balanced bracket sequence $ s $ , a pairing is a pair of positions $ (i,j) $ with $ i \lt j $ such that $ s_i $ is an opening bracket, $ s_j $ is a closing bracket, and the substring strictly between them is balanced. Consider an ordered pair $ (s,t) $ of balanced bracket sequences, where both $ s $ and $ t $ have length $ 2n $ . A pairing $ (i,j) $ is common to $ s $ and $ t $ if $ (i,j) $ is a pairing in both sequences. For example, the bracket sequences $ \texttt{(()())} $ and $ \texttt{((()))} $ have one common pairing, namely the outer pair $ (1,6) $ . Two ordered pairs $ (s,t) $ and $ (s',t') $ are considered different if $ s \ne s' $ or $ t \ne t' $ . For each $ 0 \le k \le n $ , Farmer John wants to know the number of ordered pairs $ (s,t) $ of balanced bracket sequences of length $ 2n $ with exactly $ k $ common pairings. Since these numbers may be large, output them modulo $ M $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each testcase will contain two integers, $ n $ and $ M $ ( $ 1 \leq n \leq 500 $ , $ 10^8 \leq M \leq 10^9 $ ) — half the length of the bracket sequence and the modulo to output the answer in. It is guaranteed that $ M $ is prime. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

For each testcase, output $ n + 1 $ integers, the answer modulo $ M $ for each $ 0 \leq k \leq n $ .

For the first test case, there is only one balanced bracket sequence with $ n=1 $ : $ \texttt{()} $ . It has exactly one pairing, namely $ (1,2) $ . Therefore, the only ordered pair of bracket sequences has exactly one common pairing, so the answer is $ [0,1] $ . For the second test case, there are exactly two balanced bracket sequences with $ n=2 $ : $ a=\texttt{(())} $ and $ b=\texttt{()()} $ . The pairings of $ a $ are $ (1,4) $ and $ (2,3) $ , while the pairings of $ b $ are $ (1,2) $ and $ (3,4) $ . Thus, the ordered pairs $ (a,b) $ and $ (b,a) $ have $ 0 $ common pairings, while the ordered pairs $ (a,a) $ and $ (b,b) $ have $ 2 $ common pairings. Therefore, the answer is $ [2,0,2] $ .