여느 때와 같이 배씨가 농부 존의 헛간에서 말썽을 일으키고 있습니다. 존에게는 N(1≤N≤5000) 건초 더미가 있습니다.

각 i∈[1,N]에 대해 i번째 스택에는 hi(1≤hi≤10⁹) 건초 더미가 있습니다.

배씨는 건초 더미가 떨어지는 것을 원하지 않으므로 그녀가 수행할 수 있는 유일한 작업은 다음과 같습니다.

인접한 두 더미의 높이가 정확히 1 차이가 나는 경우 더 높은 더미의 맨 위 건초더미를 더 짧은 더미로 이동할 수 있습니다.

위의 작업을 모듈로 10⁹+7로 유한하게 여러 번 수행한 후 얻을 수 있는 구성은 몇 개입니까?

모든 i에 대해 i번째 건초 더미가 모두 동일한 수의 건초 더미를 갖는 경우 두 구성은 동일한 것으로 간주됩니다.

건초 더미 세기 (Counting Haybales) timer 2초 memory 256MB

건초 더미 세기 (Counting Haybales) 2초 256MB