{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e题目描述\u003c/h1\u003e\n\u003cp\u003e你叫菜苗,你的梦想是成为一名靠味觉吃饭的人。没想到,竟然实现了。\u003c/p\u003e\n\u003cp\u003e在半年前,某品牌发布了芝士波波球口味的酸奶。此举获得了芝士爱好者们的好评,而销量当中却失去了水果味酸奶爱好者们的支持。于是他们决定研发果味芝士波波球酸奶,并请到了你,为他们品鉴酸奶。\u003c/p\u003e\n\u003cp\u003e你的胃容量限制使得你一次性不能连续喝超过n瓶酸奶,而品牌为了节省成本,自然会一次性让你喝满n瓶酸奶。同时,品牌为了节省成本,不会让你连续喝两瓶同口味的酸奶。你知道,某品牌这回一共研制了m种不同口味的水果芝士波波球酸奶,然而你不知道他们具体会以怎样的顺序依次给你什么口味的酸奶喝。\u003c/p\u003e\n\u003cp\u003e你的味觉十分灵敏,然而,如果一次性连续品尝了超过k种不同的口味,你的味觉就会失灵。为了保护珍贵的味觉,你将这件事报给了该品牌。该品牌尊重你的意愿,同时为了达到最好的收益,你知道,他们必定会让你尝满k种不同口味的酸奶。\u003c/p\u003e\n\u003cp\u003e你目前所拥有的信息就这么多,你想知道,某品牌究竟可以为你安排多少种不同的酸奶一次性品尝方案。两个方案被认为是不同的,当且仅当存在一个数i,使得在两个方案当中我将要品尝的第i瓶酸奶的口味不相同。\u003c/p\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e输入格式\u003c/h2\u003e\n\u003cp\u003e第一行一个数T,表示数据组数。T不超过300。\u003c/p\u003e\n\u003cp\u003e接下来T行,每一行描述一组数据,其中包含三个数:n,m,k。保证1\u003c\u003dn,m\u003c\u003d1e9,1\u003c\u003dk\u003c\u003d1e6, k\u003c\u003dn,m。\u003c/p\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e输出格式\u003c/h2\u003e\n对于每组数据,输出一行“Case #x: y”。其中x表示该组数据的编号(从1开始标号),y是不同的方案数,对1e9+7取模后的结果。"}},{"title":"","value":{"format":"HTML","content":"\u003ch3\u003e样例输入\u003c/h3\u003e\n\u003cpre\u003e2\n3 2 2\n3 2 1\n\u003c/pre\u003e\n\u003ch3\u003e样例输出\u003c/h3\u003e\n\u003cpre\u003eCase #1: 2\nCase #2: 0\n\u003c/pre\u003e"}}]}