시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 15 3 2 33.333%

문제

피보나치 수는 다음과 같이 정의된다

  • F[1] = 1
  • F[2] = 1
  • F[N] = F[N-1] + F[N-2] (N ≥ 2)

N개의 수가 주어져있는 집합 S와 정수 K가 주어진다.

이 때, 집합 S의 크기가 K인 부분 집합 s에 대해서, 각 부분 집합 s의 합번째 피보나치 수의 합을 구하는 프로그램을 작성하시오.

예를 들어, S = {1, 2, 3, 4, 5}, K = 2인 경우 S의 모든 부분 집합은 {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5} 이다. 각 부분 집합의 합은 3, 4, 5, 6, 5, 6, 7, 7, 8, 9 이다. F[3] + F[4] + F[5] + F[6] + F[5] + F[6] + F[7] + F[7] + F[8] + F[9] = 112 이다.

입력

첫째 줄에 N (1 ≤ N ≤ 50000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째 줄에는 집합의 각 원소가 주어진다. 집합에 들어있는 수는 109보다 작거나 같은 자연수이다.

출력

첫째 줄에 집합 S의 크기가 K인 부분 집합 s에 대해서, 각 부분 집합 s의 합번째 피보나치 수의 합을 99991로 나눈 나머지를 출력한다.

예제 입력

3 1
1 2 3

예제 출력

4

예제 입력 2

5 2
1 2 3 4 5

예제 출력 2

112

예제 입력 3

6 3
3 5 7 10 20 30

예제 출력 3

57796

힌트

출처