{"problem":{"name":"[COCI 2022/2023 #3] Bomboni","description":{"content":"Iva 是一个狂热的糖果迷！在她面前是一块填满糖果和障碍的 $n\\times n$ 的土地。Iva 目前在左上角。通过向右或向下移动，她要前往右下角。Iva 目前所在的格子没有障碍。 在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9759"},"statements":[{"statement_type":"Markdown","content":"Iva 是一个狂热的糖果迷！在她面前是一块填满糖果和障碍的 $n\\times n$ 的土地。Iva 目前在左上角。通过向右或向下移动，她要前往右下角。Iva 目前所在的格子没有障碍。\n\n在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知道一共有多少条这样的路径。由于答案可能很大，她只想知道答案模 $998244353$ 的结果。\n\n## Input\n\n第一行两个整数 $n,k$，表示土地的边长和 Iva 的最喜欢的数字。\n\n在接下来的 $n$ 行中，每一行 $n$ 个数字，描述这片土地。如果 $a_{i,j}=-1$，那么这块土地就是障碍物，否则满足这块土地包含一个 $1\\le a_{i,j}\\le 10^6$ 的数。\n\n## Output\n\n一行一个整数表示结果。\n\n[samples]\n\n## Note\n\n**【样例解释 #2】**\n\n共有三条这样的路线：\n- 5-2-3-3-1\n- 5-2-3-6-1\n- 5-7-3-6-1\n\n**【数据范围】**\n\n| 子任务 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $13$ | $n,k,a_{i,j} \\leq 20$ |\n| $2$ | $17$ | $n,k \\leq 20$ |\n| $3$ | $33$ | $k\\le 20$ |\n| $4$ | $47$ | 无特殊性质 |\n\n对于 $100\\%$ 的数据，满足 $1\\leq n \\leq 500,1\\le k\\le 10^6, -1\\le a_{i,j}\\le 10^6$。\n\n本题满分 $110$ 分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9759","tags":["2022","COCI（克罗地亚）"],"sample_group":[["2 2\n3 2\n1 4","2"],["3 6\n5 2 -1\n7 3 6\n-1 3 1","3"]],"created_at":"2026-03-03 11:09:25"}}