很神仙的一道题。

要求$[l,r]$的答案，我们可以求出$[1,r],[1,l],l$的答案，那么答案就是$[1,r]-[1,l]+l$

考虑怎么求$[1, n]$的答案。用数位dp的思想去做，设$g_{i,0/1}$表示以$i$为结尾，卡不卡上界的答案，$f_{i,0/1}$表示以$i$为结尾，卡不卡上界的子区间个数，这里不包含前导零的情况。$p_{i,0/1}$表示考虑到第$i$位，卡不卡上界的填数方案数。$F_{n}=\sum_{i=1}^ni$

考虑怎么求$g_{i,0}$：

如果之前不卡上界，那么这一位可以填$[0, m-1]$这个范围内的数，那么之前填过的数就会有$g_{i-1,0}*m*m$的贡献，第一个$m$是指进了一位，第二个$m$表示每一种状态都有$m$种填法。

如果之前卡上界，那么这一位就只能填$[0,a_i-1]$这个范围内的数，那么之前填过的数的贡献就是$g_{i-1,1}*m*a_i$。

现在我们求出了之前填的数在这一位产生的贡献，考虑填上的这个数产生了多少贡献。

第一种情况就是与之前的区间组合，即$F(m-1)*f_{i-1,0}+F(a_i-1)*f_{i-1,1}$

第二种情况就是自己单独成一个区间，即$F(m-1)*p_{i-1,0}+F(a_i-1)*p_{i-1,1}$

求$g_{i,1}$:

之前只能卡上界，那么之前的数会产生$g_{i-1,1}*m$的贡献。

新填的数的贡献就是$a_i*f_{i-1,1}+a_i*p_{i-1,1}$

求$f_{i,0}$:

如果之前不卡上界，那么这一位可以填$[0, m-1]$，那么与之前构成的方案数就是$f_{i-1,0}*m$

如果之前卡上界，那么这一位可以填$[0,a_i-1]$，那么与之前构成的方案数就是$f_{i-1,1}*a_i$

考虑这一位新产生的区间个数，就是$p_{i, 0}$，但是这样会有全是零的情况，就把全是零的方案减去，所以贡献是$p_{i,0}-1$。

求$f_{i,1}$：

只能填一个数，所以方案数就是$f_{i-1,1}+p_{i,1}$。注意这里没有前导零的情况，所以不用减$1$

$p$的转移比较显然：

$p_{i,1} = 1$

$p_{i,0} = p_{i-1, 1}*a_i+p_{i-1,0}*m$

那么最后统计答案时，以$i$为结尾的答案，不卡上界，会出现$B^{n-i}$次，卡上界时，会出现后$n-i$位形成的数次。直接加起来就行了。

贴一下代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long LL;

#define rep(x, a, b) for(int x = (a); x <= (b); ++ x)
#define per(x, a, b) for(int x = (a); x >= (b); -- x)
#define rop(x, a, b) for(int x = (a); x < (b); ++ x)
#define por(x, a, b) for(int x = (a); x > (b); -- x)

const int mod = 20130427;
void upd(int &x, int y) { x += y; if(x >= mod) x -= mod; }

const int N = 1e5 + 50;
int l[N], r[N];
int f[N][2], g[N][2], p[N][2];
int q[N], pw[N];

int F(int x) {
	if(x <= 0) return 0;
	return 1ll * x * (x + 1) / 2 % mod;
}

int F(int l, int r) {
	return (F(r) - F(l - 1) + mod) % mod;
}

int solve(int n, int *a, int m) {
	memset(f, 0, sizeof f);
	memset(g, 0, sizeof g);
	memset(p, 0, sizeof p);
	memset(pw, 0, sizeof pw);
	memset(q, 0, sizeof q);
	p[0][1] = 1; pw[n + 1] = 1;
	per(i, n, 1) q[i] = (q[i + 1] + 1ll * a[i] * pw[i + 1] % mod) % mod, pw[i] = 1ll * pw[i + 1] * m % mod;
	rep(i, 1, n) {
		p[i][1] = 1;
		p[i][0] = (1ll * p[i - 1][1] * a[i] % mod + 1ll * p[i - 1][0] * m % mod) % mod;
		f[i][1] = (f[i - 1][1] + p[i][1]) % mod;
		f[i][0] = (1ll * f[i - 1][1] * a[i] % mod + 1ll * f[i - 1][0] * m % mod + p[i][0] - 1) % mod;
		//之前出现的数产生的贡献 
		g[i][0] = (1ll * g[i - 1][0] * m % mod * m % mod + 1ll * g[i - 1][1] * m % mod * a[i] % mod) % mod; // 之前的每个合法状态的贡献都会*m，然后乘后面可以放的数的个数。 
		g[i][1] = 1ll * g[i - 1][1] * m % mod;
		//新填的数产生的贡献 
	    upd(g[i][0], 1ll * F(a[i] - 1) * f[i - 1][1] % mod); //在之前的卡上界的合法状态中放一个[0,a[i]-1]，这个数与之前的状态产生的贡献。 
	    upd(g[i][0], F(a[i] - 1) * p[i - 1][1]); //  这个数单独贡献。
		if(i != 1) {
			upd(g[i][0], 1ll * F(m - 1) * f[i - 1][0] % mod); // 在之前不卡上界的时候放一个数。 
			upd(g[i][0], 1ll * F(m - 1) * p[i - 1][0] % mod); // 这个数单独贡献。 
		}
		upd(g[i][1], 1ll * a[i] * f[i - 1][1] % mod);
		upd(g[i][1], a[i]);
	}
	int ans = 0;
	rep(i, 1, n) {
		upd(ans, g[i][1] * 1ll * (q[i + 1] + 1) % mod);
		upd(ans, g[i][0] * 1ll * pw[i + 1] % mod);
	}
	return ans;
}

int calc(int n, int *a, int m) {
	memset(pw, 0, sizeof pw);
	memset(q, 0, sizeof q);
	int ans = 0; pw[1] = 1; q[1] = 1;
	rep(i, 2, n) pw[i] = 1ll * pw[i - 1] * m % mod, q[i] = (q[i - 1] + pw[i]) % mod;
	rep(i, 1, n) upd(ans, 1ll * i * a[i] % mod * q[n - i + 1] % mod);
	return ans;
}

int main() {
	int m; scanf("%d", &m);
	int l1, l2;
	scanf("%d", &l1); rep(i, 1, l1) scanf("%d", &l[i]);
	scanf("%d", &l2); rep(i, 1, l2) scanf("%d", &r[i]);
	printf("%lld\n", (((solve(l2, r, m) - solve(l1, l, m) + 1ll * calc(l1, l, m)) % mod) + mod) % mod);
}

//代码写的丑，不建议分析代码qwq。我自己看着都头疼qwq。
#include <algorithm>
#include <cstdio>
#include <cstring>
typedef long long LL;
const int N = 100050;
const int mod = 20130427;
int n, m, B;
int L[N], R[N];
LL SB[N], S[N];
LL a[N][2], s[N][2], ss[N][2], sl[N][2];
int solve(int *p, int l) {
  memset(a, 0, sizeof a);
  memset(s, 0, sizeof s);
  memset(ss, 0, sizeof ss);
  memset(sl, 0, sizeof sl);
  a[l][0] = 1;
  for (int i = l - 1; ~i; --i) {
    int c = (i == l - 1 ? 0 : B);
    a[i][0] = a[i + 1][0];
    a[i][1] = (c - 1 + a[i + 1][1] * B + a[i + 1][0] * p[i]) % mod;
    sl[i][0] = sl[i + 1][0] + a[i + 1][0];
    sl[i][1] = (c - 1 + sl[i][0] * p[i] + (sl[i + 1][1] + a[i + 1][1]) * B) % mod;
    ss[i][0] = (ss[i + 1][0] * B + p[i] * sl[i][0]) % mod;
    ss[i][1] = (S[c] + ss[i + 1][0] * B * p[i] + S[p[i]] * sl[i][0] + ss[i + 1][1] * B % mod * B + S[B] * (sl[i + 1][1] + a[i + 1][1])) % mod;
    s[i][0] = (s[i + 1][0] + ss[i][0]) % mod;
    s[i][1] = (s[i + 1][0] * p[i] + s[i + 1][1] * B + ss[i][1]) % mod;
  }
  return (s[0][0] + s[0][1]) % mod;
}
int main() {
  scanf("%d", &B);
  SB[0] = 1;
  for (int i = 0; i < N - 1; ++i) SB[i + 1] = (SB[i] * B + 1) % mod;
  S[0] = 0;
  for (int i = 0; i < B; ++i) S[i + 1] = (S[i] + i) % mod;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &L[n - i - 1]);
  for (int i = 0; i < n; ++i) {
    if (L[i] > 0) {
      --L[i];
      break;    }
    L[i] = B - 1;
  }
  if (!L[n - 1]) --n;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) scanf("%d", &R[m - i - 1]);
  printf("%d\n", (solve(R, m) - solve(L, n) + mod) % mod);
  return 0;
}