IOI가 곧 일본의 츠쿠바 시에서 열린다(2018년 IOI가 일본에서 열렸다.).IOI를 준비하기 위해, 츠쿠바 시의 중심 거리에 고층 건물을 건축하는 계획을 세우고 있다. 전망이 좋은 장소를 새로 만들고 싶기 때문에, 건축할 때 아래와 같은 조건을 만족해야 한다.

높이가 각각 A_1 , A_2 , A_3 , ... ,A_N인 N개의 건물을 짓고자 한다. N개의 건물의 순서를 아직 결정하지 않았기 때문에 필요하다면 건물의 순서를 마음대로 바꿀 수 있다. 이제 IOI를 맞이하여 그들을 꾸밀 것이다. 꾸미는 데 필요한 재료가 한정적이기 떄문에, 인접한 두 건물의 높이 차의 합이 L이하여야 한다. 다시 말해서, 재배열한 건물의 높이가 f_1 , f_2 , f_3 , ... , f_N 순서일 때 | f_1 - f_2 | + | f_2 - f_3 | + ... + | f_{N-1} - f_N | <= L을 만족해야 한다. 여기서 |x|는 x의 절댓값을 의미한다.

건물의 배열 중 위의 조건을 만족하는 개수는 몇 개인가?

건물의 수 N, 건물의 높이, 인접한 건물 사이 높이 차 합의 최대값인 L이 주어졌을 때, 조건을 만족하는 건물의 배열의 수를 출력하는 프로그램을 작성하여라. 답이 너무 커질 수 있으므로 1 000 000 007으로 나눈 나머지를 구하여라.

#4954 upload 70 done 14 how_to_reg 13

마천루 timer 2s memory 512MB

#4954

마천루 2s 512MB