在歌唱王国，所有人的名字都是一个非空的仅包含整数1~n的字符串。王国里生活着一大群咕噜兵，他们靠不停的
歌唱首领——牛人酋长们的名字来获取力量。咕噜兵每一次歌唱过程是这样的：首先，他从整数生成器那儿获得一
个数字，然后花一个时间单位将此数字唱出来，如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱
序列的一个连续子串），那么这次歌唱过程就立即结束。相关名词定义歌唱序列：如果某人歌唱了x个数字，第i次
歌唱的数字为ai，那么歌唱序列=(a1,a2,…,ax)。整数生成器：歌唱王国的神物，它有一个按钮，如果你按一下按
钮，将从1~n数字中等概率的随机返回一个整数。歌唱时间：在一次歌唱过程中花费的时间。歌唱时间是随机的，
无法预料；不过歌唱时间的期望值是固定的，此期望值即平均来说歌唱时间有多长，亦可称作平均歌唱时间。王国
里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢免一些牛人酋长，使得平均歌唱时间变长。
但是他们不能罢免掉所有的牛人酋长，否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛
人酋长而罢免其余的牛人酋长。你的任务是：对于给定的n、牛人酋长的个数t以及每一个牛人酋长的名字，告诉王
国里的人们，对于1≤i≤t，如果保留第i个牛人酋长，罢免掉其余的，那么平均歌唱时间将是多少。提示：此数为
一个非负整数！输出要求：由于这个数字太大，所以你只需输出这个数的末4位数字。如果不足4位，则前面补0(见
样例)。
BZPRO