13278번 - 피보나치 합의 개수

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

• 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)이 주어진다.

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

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