다항함수의 미분과 나머지

$6$개의 정수 $n$, $d$, $m$, $k$, $a$, $b$와 정수열 $s=(s\_0, s\_1, \cdots, s\_d)$가 주어진다.

다음을 모두 만족하는 모든 정수열 $c=(c\_0, c\_1, \cdots, c\_n)$들의 집합을 $A$라 하자.

• 모든 정수 $i$ ($0 \le i \le n$)에 대해 $a \le c\_i \le b$

• 다음을 모두 만족하는 함수 $f \colon \mathbb R \to \mathbb R$와 정수열 $r=(r\_0, r\_1, \cdots, r\_d)$가 존재한다.

  • 모든 실수 $t$에 대해 $f(t) = \sum\_{i=0}^{n} c\_i t^i$
  • 모든 실수 $t$에 대해 $f^{(k)}(t) = \sum\_{j=0}^{d} r\_j t^j$
  • 모든 정수 $j$ ($0 \le j \le d$)에 대해 $r\_j \bmod m = s\_j$

집합 $A$의 크기와 $A$의 원소 중 사전 순으로 가장 작은 원소를 구해 보자.

첫 번째 줄에 $6$개의 정수 $n$, $d$, $m$, $k$, $a$, $b$가 공백으로 구분되어 주어진다.

두 번째 줄에 $d+1$개의 정수 $s\_0$, $s\_1$, $\cdots$, $s\_d$가 공백으로 구분되어 주어진다.

첫 번째 줄에 $|A| \bmod (10^9+7)$의 값을 출력한다.

만약 $A$가 공집합이 아니라면, $A$에 속하는 정수열 중 사전 순으로 가장 작은 것을 $p$라 할 때, 두 번째 줄에 $n+1$개의 정수 $p\_0$, $p\_1$, $\cdots$, $p\_n$을 공백으로 구분하여 출력한다.

• $0 \le n \le 10^5$
• $0 \le d \le 10^5$
• $1 \le m \le 10^9$
• $0 \le k \le 10^9$
• $0 \le a \le b \le 10^9$
• 모든 정수 $j$ ($0 \le j \le d$)에 대해 $0 \le s\_j < m$

• $f^{(k)}$는 함수 $f$를 $k$번 미분해서 얻은 함수이다.

  • $f^{(0)} = f$
  • 모든 양의 정수 $k$에 대해 $f^{(k)} = (f^{(k-1)})'$

• 모든 실수 $x$에 대해 $x^0=1$로 본다.

• $\mathbb R$는 실수 전체의 집합이다.

• $x \bmod y$는 $x$를 $y$로 나눈 나머지이다.

• $|A|$는 집합 $A$의 크기이다.

• 정수열 $x=(x\_0, x\_1, \cdots, x\_l)$가 정수열 $y=(y\_0, y\_1, \cdots, y\_l)$보다 사전 순으로 작다는 것은 다음을 모두 만족하는 정수 $h$ ($0 \le h \le l$)가 존재한다는 의미이다.

  • $x\_h < y\_h$
  • 모든 정수 $i$ ($0 \le i < h$)에 대해 $x\_i=y\_i$