给定整数nmk，和一个长度为m1的正整数数组v0​v1​vm​。对于一个长度为n，下标从1开始且每个元素均不超过m的非负整数序列ai​，我们定义它的权值为va1​​×va2​​×⋯×van​​。当这样的序列ai​满足整数S2a1​2a2​⋯2an​的二进制表示中1的个数不超过k时，我们认为ai​是一个合法序列。计算所有合法序列ai​的权值和对998244353取模的结果。

大家都知道喷泉吧？现在有一个喷泉由N个圆盘组成，从上到下以此编号为1∼N，第i个喷泉的直径为Di​，容量为Ci​，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径大于这个圆盘的圆盘里。如果下面没有满足要求的圆盘，水就会流到喷泉下的水池里。现在给定QRi​Vi​如果最终流入了水池里，那么输出0。