{"raw_statement":[{"iden":"statement","content":"给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。\n\n两个序列 $(a_1,a_2,\\cdots,a_n)$ 与 $(b_1,b_2,\\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\\neq b_i$。\n\n由于答案可能很大，请输出答案对 $998\\ 244\\ 353$ 取模后的结果。"},{"iden":"input","content":"输入的第一行包含一个整数 $Q$ 表示询问次数。\n\n接下来 $Q$ 行，每行包含三个整数 $x,y,n$ 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。\n"},{"iden":"output","content":"输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。"},{"iden":"note","content":"对于 $40\\%$ 的评测用例，$n\\le 30$；  \n对于 $70\\%$ 的评测用例，$n\\le 5000$；  \n对于所有评测用例，$1\\le Q\\le 100$，$2\\le n\\le 10^5$，$1\\le x,y\\le 10^9$。"}],"translated_statement":null,"sample_group":[["3\n3 6 2\n12 144 3\n233 251640 10","2\n72\n905954656"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}