N이 최대 300일때 1~ N까지의 수로 이루어진 수열 중 수가 커졌다 작아졌다하는 수열의 개수


예를들면 N 이 5일때 1 3 2 5 4, 3 2 5 1 4는 커졌다 작아졌다 반복함 근데 3 2 1 5 4는 3 2 에서 작아지고 2 1에서 또 작아지니까 만족하지 않음

설명이 좆같은데  N=3일때
만족하는 수열 3 1 2, 1 3 2, 2 1 3, 2 3 1
만족하지 않는 수열 1 2 3, 3 2 1

이런 수열 개수의 나머지 구하는 문제였는데 어케푸는거냐 도와줄 고인물있냐