E - Modular Inverse Points of Products Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君はお店で買い物をしています。

お店には N 個の商品が並んでおり、各商品には 1 から N までの番号が付けられています。商品 i の価格は A_i です。価格が同じ商品が複数存在することもありますが、番号が異なれば異なる商品として区別します。

高橋君はこの中から K 個の商品を選んで購入します。同じ商品を複数回選ぶことはできず、選ぶ順序も区別しません（すなわち、N 個から K 個を選ぶ組み合わせとして選びます）。選んだ K 個の商品の価格の積を P とします。

このお店では特別なポイント制度があり、購入した商品の組み合わせに対して、素数 M を用いた以下のルールでポイントが付与されます。

  • P が M の倍数でない場合：P \cdot Q \equiv 1 \pmod{M} かつ 0 \leq Q < M を満たす整数 Q がただ 1 つ存在します（M が素数であることから保証されます）。この Q を M を法とした P の乗法逆元と呼び、Q がポイントとして付与されます。
  • P が M の倍数である場合：乗法逆元が存在しないため、付与されるポイントは 0 とします。

N 個の商品から K 個を選ぶ \binom{N}{K} 通りすべての選び方について、それぞれ付与されるポイントを求め、その総和を M で割った余りを出力してください。

制約

  • 1 \leq K \leq N \leq 5000
  • 2 \leq M \leq 10^9
  • M は素数である
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N K M
A_1 A_2 \ldots A_N
  • 1 行目には、商品の個数を表す整数 N、選ぶ個数を表す整数 K、素数 M が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格を表す整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

すべての選び方における付与ポイントの総和を M で割った余りを 1 行で出力せよ。出力は 0 以上 M - 1 以下の整数となる。

入力例 1

4 2 7
1 2 3 4

出力例 1

0

入力例 2

5 3 5
5 1 2 10 3

出力例 2

1

入力例 3

12 5 101
3 202 7 15 101 48 7 99 100 250 13 1

出力例 3

12

入力例 4

30 15 998244353
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 998244353 999999937 123456789 987654321 314159265

出力例 4

354173354

入力例 5

1 1 2
2

出力例 5

0

Score : 433 pts

Problem Statement

Takahashi is shopping at a store.

The store has N products lined up, each numbered from 1 to N. The price of product i is A_i. Multiple products may have the same price, but products with different numbers are distinguished as different products.

Takahashi will select and purchase K products from these. He cannot select the same product more than once, and the order of selection does not matter (that is, he selects as a combination of K items from N). Let P be the product of the prices of the K selected items.

This store has a special point system where points are awarded for the combination of purchased products according to the following rules using a prime number M:

  • If P is not a multiple of M: There exists exactly one integer Q satisfying P \cdot Q \equiv 1 \pmod{M} and 0 \leq Q < M (this is guaranteed since M is prime). This Q is called the multiplicative inverse of P modulo M, and Q points are awarded.
  • If P is a multiple of M: Since the multiplicative inverse does not exist, the awarded points are 0.

For all \binom{N}{K} ways of choosing K products from N products, determine the points awarded for each selection, and output the remainder when the total sum is divided by M.

Constraints

  • 1 \leq K \leq N \leq 5000
  • 2 \leq M \leq 10^9
  • M is a prime number
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers

Input

N K M
A_1 A_2 \ldots A_N
  • The first line contains the integer N representing the number of products, the integer K representing the number to select, and the prime M, separated by spaces.
  • The second line contains the integers A_1, A_2, \ldots, A_N representing the prices of each product, separated by spaces.

Output

Output in one line the remainder when the total sum of awarded points over all selections is divided by M. The output will be an integer between 0 and M - 1, inclusive.

Sample Input 1

4 2 7
1 2 3 4

Sample Output 1

0

Sample Input 2

5 3 5
5 1 2 10 3

Sample Output 2

1

Sample Input 3

12 5 101
3 202 7 15 101 48 7 99 100 250 13 1

Sample Output 3

12

Sample Input 4

30 15 998244353
1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 998244353 999999937 123456789 987654321 314159265

Sample Output 4

354173354

Sample Input 5

1 1 2
2

Sample Output 5

0