다항함수의 미분과 나머지

$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$