某星球国家共有n个城市，编号0至n-1，第i个城市有i+1个市民。一开始所有城市之间都不连通。

现在进行Y年道路建设期，编号0至Y-1，在第i年的6月份，会建好一道道路，链接城市A[i]和B[i]，

同年12月份，国家的每个市民都会向全国的其他每一个市民寄一张贺卡，如果道路能送达（即有路径到达），那么贺卡就会被寄出，

否则贺卡会被邮局销毁。问题是：Y年建设期总共有多少贺卡会被寄出？答案模1000000007。

输入格式

第一行，三个整数，n, Y, seed。1<=n<=10^9。1<=Y<=150000。0<=seed<=2^31-1。

其中seed的作用是用来产生A数组和B数组的，它们产生的规则是：

其中modulo是取模的意思。

输出格式

一个整数。

7 1 47

112