P5109 归程

dkw在玩一款叫做《ION8102》的游戏，这个游戏分为序章，第一章，第二章。 她已经满血通过了序章，来到了第一章的第一关。 这关的名字叫归程，她需要到达指定地点，这一路上要经过 $m$ 扇机关门。 每扇机关门上有一个钥匙孔，只有特制钥匙可以放进去，里面有 $k$ 把转轮锁，每个转轮锁都要恰好转到目标位置 $a_i$ 才能开门，每个转轮锁的最大刻度都是 $v$ ，刻度标号从 $0$ 到 $v$ ，每个转轮锁初始位置都是 $0$ 。 dkw身上有 $n$ 把钥匙，每把钥匙都有 $k$ 个转动量 $b_i$ ，分别代表这把钥匙转一圈，可以让机关门中的这个转轮锁走多少个位置。 每扇机关门还有一个圈数限制 $c$ ，也就是你总共只能用钥匙转最多 $c$ 圈，并且每把钥匙只能正着转，只能转整数圈。 任务要求顺次打开这 $m$ 扇门，这么简单的问题dkw当然秒了，但是dkw好奇的是：对于每一扇门，有多少种方案能顺利打开呢？ 两种方案不同，当且仅当两种方案中总圈数不同或某一圈所用钥匙不同。 如果你解答了dkw的好奇心，那么你将会收到她的一份大~礼物——100分！

无

无

本题采用子任务测试。 - 子任务1 (9pts)：$1\le n,m,k,c,v\le 5$ - 子任务2 (16pts)：$1\le n\le 10^5,1\le m,c\le 100,v=1,k\le 12$ - 子任务3 (17pts)：$1\le n\le 10^5,1\le m,c\le 100,v=2,k\le 8$ - 子任务4 (19pts)：$1\le n\le 10^5,1\le m,c\le 100,v=3,k\le 6$ - 子任务5 (16pts)：$1\le n\le 10^5,1\le m,c\le 100$ - 子任务6 (23pts)：$1\le n\le 10^5,1\le m\le 5,1\le c\le 10^9$ 每个测试点的 $v$ 和 $k$ 会从下表的对应关系中选取。 其中 $maxk$ 代表 $k$ 不会超过该值。 | 编号 | v | maxk | | ---- | ---- | ---- | | 1 | 1 | 12 | | 2 | 2 | 8 | | 3 | 3 | 6 | | 4 | 4 | 5 | | 5 | 5 | 4 | | 6 | 6 | 4 | | 7 | 7 | 3 | | 8 | 8 | 3 | | 9 | 9 | 3 |