/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は高校の新入生で、これから参加する部活動を決めようとしています。
高橋君の学校には N 個の部活動があり、それぞれの部活動には「活動ポイント」が設定されています。 i 番目の部活動の活動ポイントは A_i です。
高橋君は複数の部活動を掛け持ちすることができますが、独自のこだわりがあります。
- 選んだ部活動の活動ポイントの合計が K の倍数になるような組み合わせを「バランスが良い」とみなします。
- 何も部活動に入らない（空の組み合わせ）は、高校生活として寂しいため、認められません。
高橋君は、バランスが良い部活動の組み合わせが何通りあるかを知りたいと思っています。
N 個の部活動から 1 つ以上を選ぶ方法のうち、選んだ部活動の活動ポイントの合計が K の倍数となるような選び方の総数を求めてください。答えは非常に大きくなる可能性があるため、 10^9 + 7 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq K \leq 100
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、部活動の数を表す N と、倍数の基準となる値 K が、スペース区切りで与えられる。
- 2 行目には、各部活動の活動ポイントを表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
選んだ部活動の活動ポイントの合計が K の倍数となるような、 1 つ以上の部活動の選び方の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 1
3 3 1 2 3
出力例 1
3
入力例 2
5 4 2 4 6 8 10
出力例 2
15
入力例 3
10 7 7 14 21 1 2 3 4 5 6 49
出力例 3
159
Score : 366 pts
Problem Statement
Takahashi is a new high school student who is trying to decide which club activities to join.
There are N club activities at Takahashi's school, and each club activity has an "activity point" value assigned to it. The activity points of the i-th club activity is A_i.
Takahashi can join multiple club activities simultaneously, but he has his own particular preferences.
- He considers a combination "well-balanced" if the total activity points of the chosen club activities is a multiple of K.
- Joining no club activities (the empty combination) is not allowed, as it would make for a lonely high school life.
Takahashi wants to know how many well-balanced combinations of club activities exist.
Among all ways to choose 1 or more club activities from the N available, find the total number of ways such that the sum of activity points of the chosen club activities is a multiple of K. Since the answer can be very large, output it modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq K \leq 100
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains N, the number of club activities, and K, the value for the multiple criterion, separated by a space.
- The second line contains A_1, A_2, \ldots, A_N, the activity points of each club activity, separated by spaces.
Output
Output in a single line the number of ways to choose 1 or more club activities such that the total activity points is a multiple of K, modulo 10^9 + 7.
Sample Input 1
3 3 1 2 3
Sample Output 1
3
Sample Input 2
5 4 2 4 6 8 10
Sample Output 2
15
Sample Input 3
10 7 7 14 21 1 2 3 4 5 6 49
Sample Output 3
159