OMC146(D)

点数: 500

Writer: sakurano

　整数 $a_1, a_2, \ldots, a_{5758}$ は $1\leq a_1\lt a_2 \lt\cdots\lt a_{5758}\leq 3001^2$ をみたしています．このとき，$U=\{a_1,a_2,\ldots, a_{5758}\}$ とし，$U$ の部分集合 $S$ に対し，整数 $f(S)$ を以下のように定めます．

• 各 $i=1,2,\dots,5758$ に対し，$S_i$ で $S$ の要素のうち $a_i$ 以下のもの全体のなす集合を表すとき，$$f(S)=\sum_{i=1}^{5758}\bigl(\vert S_i \vert-2\max S_i\bigr)$$ とする．ただし，集合 $X$ に対し，$X$ の要素数を $\vert X \vert$，$X$ の要素のうち最大のものを $\max X$ で表す．また，ここでは $\max \emptyset = 0$ とする．

　$f(S)\lt f(U)$ となる集合 $S\subset U$ が存在するような整数の組 $(a_1, a_2, \dots, a_{5758})$ としてあり得るものは $M$ 通りあります．$M$ を素数 $3001$ で割った余りを求めてください．