Tree Depth timer 2s memory 512MB

새해를 맞아, Farmer John은 소들에게 축제 분위기의 이진 탐색 트리(BST)를 선물하기로 했다!

BST를 생성하기 위해, FJ는 먼저 정수 1\ldots N의 순열 a=\{a_1,a_2,\ldots,a_N\}을 하나 고른다. 여기서 N\le 300이다. 이후 FJ는 인자 1과 N으로 아래 의사코드를 실행한다.

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

예를 들어, 순열 \{3,2,5,1,4\}는 다음과 같은 BST를 생성한다.

    4
   / \
  2   5
 / \ 
1   3

d_i(a)를 순열 a에 의해 생성된 트리에서 노드 i의 깊이(depth)라고 하자. 이는 노드 i에서 루트까지의 경로에 포함된 노드의 개수이다. 위 예시에서 d_4(a)=1, d_2(a)=d_5(a)=2, 그리고 d_1(a)=d_3(a)=3이다.

순열 a의 inversion 개수는 1\le i<j\le N이고 a_i>a_j를 만족하는 정수 쌍 (i,j)의 개수이다. 소들은 FJ가 사용할 순열 a가 정확히 K개의 inversion을 가진다는 사실을 알고 있다 (0\le K\le \frac{N(N-1)}{2}).

이 조건을 만족하는 모든 a에 대해, 각 1\le i\le N에 대하여 \sum_a d_i(a)를 계산한 뒤 M으로 나눈 나머지를 구하여라.