农夫约翰有 头牛，编号依次为 ，每头牛都有一个整数值的体重 ；约翰准备参加农场技艺大赛，向广大的农业社区展示他的奶牛。
大赛规则允许约翰带 头牛参赛. 约翰给每头牛赋予了一个「有用度」，它表示了某头牛在比赛中的有用程度. 约翰希望他选出的奶牛的有用度之和最大。
有可能选出很多组的 头牛都能达到有用度最大和. 约翰害怕选出的 头牛的总重量会给大赛带来震撼，所以，要考虑优先选择体重轻的奶牛。
帮助约翰选出 头总重量最轻，并且有用度之和最大的奶牛. 输出体重模 后的余数。
注意：为了使输入更快，约翰使用了一个多项式来生成每头牛的体重和有用度，对每头牛 ，体重和有用度的计算公式为：
这个多项式有时会生成重复的数，你的程序要正确处理这种情况。
