문제
배열 $A$가 있습니다. 처음에 $A$는 빈 배열입니다. 다음과 같은 조작을 $M$번 해서 배열 $A$를 채웁니다.
- $K$와 정수열 $B_1, \cdots, B_N$이 주어집니다. $A$의 가장 뒤에 $B_1, B_2, \cdots, B_N$을 차례로 이어붙이는 것을 $K$ 번 반복합니다.
이렇게 만들어진 배열 $A_1, A_2, \cdots, A_{\lvert A \rvert}$에 대해 다음 조건을 만족시키는 $(i, j)$ 정수쌍의 개수를 출력하세요.
- 1ドル \le i < j \le \lvert A \rvert$
- $A_i > A_j$
출력
문제의 조건을 만족시키는 $(i, j)$ 정수쌍의 개수를 출력하세요. 단, 수가 매우 커질 수 있으니 1ドル,000円,000円,007円 (= 10^9+7)$로 나눈 나머지를 출력하세요. 1ドル,000円,000円,007円$은 소수입니다.
조작이 끝난 이후 $A$는 $[3, 1, 4, 1, 3, 1, 4, 1, 5, 5, 5]$ 입니다.
W3sicHJvYmxlbV9pZCI6IjI4NzA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUkxFIEludmVyc2lvbiBDb3VudGluZyIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzMwXHVjNWY0ICRBJFx1YWMwMCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMCAkQSRcdWIyOTQgXHViZTQ4IFx1YmMzMFx1YzVmNFx1Yzc4NVx1YjJjOFx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWM3OTFcdWM3NDQgJE0kXHViYzg4IFx1ZDU3NFx1YzExYyBcdWJjMzBcdWM1ZjQgJEEkXHViOTdjIFx1Y2M0NFx1YzZjMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kSyRcdWM2NDAgXHVjODE1XHVjMjE4XHVjNWY0ICRCXzEsIFxcY2RvdHMsIEJfTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkQSRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YjRhNFx1YzVkMCAkQl8xLCBCXzIsIFxcY2RvdHMsIEJfTiRcdWM3NDQgXHVjYzI4XHViODQwXHViODVjIFx1Yzc3NFx1YzViNFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NDQgJEskIFx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0XHViODA3XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWJjMzBcdWM1ZjQgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX3tcXGx2ZXJ0IEEgXFxydmVydH0kXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCAkKGksIGopJCBcdWM4MTVcdWMyMThcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSBcXGxlIGkgJmx0OyBqIFxcbGUgXFxsdmVydCBBIFxccnZlcnQkPFwvbGk+XHJcblx0PGxpPiRBX2kgJmd0OyBBX2okPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjODcwXHVjNzkxXHVjNzU4IFx1ZDY5Zlx1YzIxOCAkTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkKDEgXFxsZSBNIFxcbGUgNTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTSRcdWJjODhcdWM3NTggXHVjODcwXHVjNzkxXHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHViNDUwIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjICRNJFx1YmM4OCBcdWI0ZTRcdWM1YjRcdWM2MzVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM4NzBcdWM3OTFcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4NzBcdWM3OTFcdWM3NTggXHVkNjlmXHVjMjE4ICRLJFx1YzY0MCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0ICROJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgSyBcXGxlIDEwXjk7JCAkMSBcXGxlIE4gXFxsZSA1MDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0ICRCXzEsIEJfMiwgXFxjZG90cywgQl9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgQl9pIFxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwICROJFx1Yzc1OCBcdWQ1NjlcdWM3NDAgJDUwMFxcLDAwMCQgXHVjNzc0XHVkNTU4XHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0ICQoaSwgaikkIFx1YzgxNVx1YzIxOFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LiBcdWIyZTgsIFx1YzIxOFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWIyYzggJDFcXCwwMDBcXCwwMDBcXCwwMDcgKD0gMTBeOSs3KSRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuICQxXFwsMDAwXFwsMDAwXFwsMDA3JFx1Yzc0MCBcdWMxOGNcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1Yzg3MFx1Yzc5MVx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVjNzc0XHVkNmM0ICRBJFx1YjI5NCAkWzMsIDEsIDQsIDEsIDMsIDEsIDQsIDEsIDUsIDUsIDVdJCBcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjg3MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSTEUgSW52ZXJzaW9uIENvdW50aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSBhbiBhcnJheSAkQSQuIEluaXRpYWxseSwgJEEkIGlzIGFuIGVtcHR5IGFycmF5LiBGaWxsIHRoZSBhcnJheSAkQSQgYnkgcGVyZm9ybWluZyB0aGUgZm9sbG93aW5nIG9wZXJhdGlvbiAkTSQgdGltZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WW91IGFyZSBnaXZlbiAkSyQgYW5kIGFuIGludGVnZXIgc2VxdWVuY2UgJEJfMSwgXFxjZG90cywgQl9OJC4gQXBwZW5kICRCXzEsIEJfMiwgXFxjZG90cywgQl9OJCB0byB0aGUgZW5kIG9mICRBJCBmb3IgJEskIHRpbWVzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciB0aGUgcmVzdWx0aW5nIGFycmF5ICRBXzEsIEFfMiwgXFxjZG90cywgQV97XFxsdmVydCBBIFxccnZlcnR9JCwgb3V0cHV0IHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgaW50ZWdlcnMgJChpLCBqKSQgdGhhdCBzYXRpc2Z5IHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxIFxcbGUgaSAmbHQ7IGogXFxsZSBcXGx2ZXJ0IEEgXFxydmVydCQ8XC9saT5cclxuXHQ8bGk+JEFfaSAmZ3Q7IEFfaiQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBvcGVyYXRpb25zICRNJC4gJCgxIFxcbGUgTSBcXGxlIDUwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0ICRNJCBwYWlycyBvZiBsaW5lcyBjb250YWluIGluZm9ybWF0aW9uIGFib3V0IHRoZSAkTSQgb3BlcmF0aW9ucyBpbiBvcmRlci48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgZWFjaCBvcGVyYXRpb24gY29udGFpbnMgdGhlIG51bWJlciBvZiByZXBldGl0aW9ucyAkSyQgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGFycmF5ICROJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMSBcXGxlIEsgXFxsZSAxMF45OyQgJDEgXFxsZSBOIFxcbGUgNTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgZWxlbWVudHMgb2YgdGhlIGFycmF5ICRCXzEsIEJfMiwgXFxjZG90cywgQl9OJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMSBcXGxlIEJfaSBcXGxlIDEwXjkpJDxcL3A+XHJcblxyXG48cD5UaGUgdG90YWwgc3VtIG9mIGFsbCAkTiQgZ2l2ZW4gaW4gdGhlIGlucHV0IGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byAkNTAwXFwsMDAwJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBpbnRlZ2VycyAkKGksIGopJCB0aGF0IHNhdGlzZnkgdGhlIGNvbmRpdGlvbnMgb2YgdGhlIHByb2JsZW0uIFNpbmNlIHRoZSBudW1iZXIgY291bGQgYmUgdmVyeSBsYXJnZSwgb3V0cHV0IHRoZSByZW1haW5kZXIgYWZ0ZXIgZGl2aWRpbmcgYnkgJDFcXCwwMDBcXCwwMDBcXCwwMDcgKD0gMTBeOSs3KSQuICQxXFwsMDAwXFwsMDAwXFwsMDA3JCBpcyBhIHByaW1lIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkFmdGVyIHRoZSBvcGVyYXRpb25zLCAkQSQgYmVjb21lcyAkWzMsIDEsIDQsIDEsIDMsIDEsIDQsIDEsIDUsIDUsIDVdJC48XC9wPlxyXG4ifV0=