아라비안나이트를 들려 준 셰에라자드 왕비의 이야기에 따르면, 어떤 사막의 한복판엔 호수가 하나 있었다고 한다.

원래 이 호수에는 F 마리의 물고기가 살았다.

그리고 이 땅에서 가장 귀중한 보석들이 K 종류 선정되어 모든 물고기들이 이 보석을 한 덩이씩 삼켰다.

K의 값은 F보다 작을 수 있기 때문에 동일한 종류의 보석을 두 마리 이상의 물고기가 먹었을 수도 있다.

시간이 흐르면서 어떤 물고기는 다른 물고기를 잡아먹기도 했다.

물고기는 몸길이가 자신의 절반 이하인 것만 잡아먹을 수 있다. (물고기 A가 물고기 B를 잡아먹기 위해서는 LA ≥ 2×LB여야만 한다.)

물고기가 언제 다른 물고기를 잡아먹는지에 대해서는 특별한 규칙이 없다.

어떤 물고기는 자기보다 충분히 작은 물고기들을 수차례 잡아먹었을 수 있으나,

어떤 물고기는 다른 물고기를 잡아먹을 수 있는데도 그렇게 하지 않았을 수도 있다.

다른 물고기를 잡아먹은 물고기는 몸길이는 변하지 않으나, 잡아먹힌 물고기의 뱃속에 있던 보석을 자기 뱃속에 고스란히 갖고 있게 된다.

모든 물고기에 보석이 들어있는 이 호수를 찾아낼 수만 있다면 당신은 물고기를 잡아 뱃속의 모든 보석을 차지할 수 있다고 셰에라자드 왕비는 말했다.

이제 당신의 운을 시험할 때가 온 것이다.

하지만 호수를 찾아 긴 여행을 떠나기에 앞서, 당신은 물고기를 하나 잡았을 때 얻을 수 있는 보석들의 조합 가짓수가 얼마나 존재할지 알고 싶어 한다.

물고기들의 몸길이와 초창기에 이들이 하나씩 삼킨 보석들의 종류 수를 입력 받아,

물고기를 아무거나 하나 잡았을 때 이 물고기의 뱃속에 있을 수 있는 보석의 조합 가짓수를 찾아서

이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

한 조합이란 K개의 종류별 보석 개수만으로 구성된다. 보석을 얻은 순서라든가, 종류가 같은 두 보석끼리는 구분을 하지 않는다.

이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

물고기(Fish) timer 3s memory 64MB

물고기(Fish) 3s 64MB