[传智杯 #3 决赛] 旅人1969

在被称为未来的二十一世纪里，只残留着不安与少许的幻想。 永远与须臾的罪人啊，二十世纪的诺亚方舟，承载着期待与不安向着天空飞去呢！ 而作为希望的你，在这并不永恒的旅途中，会怎样地前行呢？

一条笔直的公路上有 $n$ 个旅店，第 $i$ 个旅店的坐标是 $i$，每一天早上从旅店出发走最多 $m$ 个距离，同时固定给你一个常数 $k$。 给定 $q$ 组询问，每次给定 $u,v$，求早上从旅店 $u$ 出发到旅店 $v$，途径不超过 $k$ 个旅店（不含起点 $u$）且行走方向不变的方案数。两种方案不同当且仅当存在一个不同的旅店选择，答案对 $998244353$ 取模。 对于所有数据，$n,q\leq 10^5$，$m,k\leq 10^4$，$mk\leq 10^5$，$u,v\leq n$。

输入共 $q+1$ 行。 第一行输入 $4$ 个正整数 $n,m,k,q$。 接下来 $q$ 行，每行输入 $2$ 个正整数 $u,v$，表示一组询问。

输出共 $q$ 行，每行输入 $1$ 个整数表示答案。

3 2 2 2
1 3
2 3

2
1

2077 30 200 3
1949 2021
1969 2077
1970 2004

360658315
804081653
603979748