문제
하바는 최근 학교에서 수열과 함수에 대해 배웠다. 배운 것을 바로 적용하는 성격의 하바는 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $D$를 반환하는 함수 $d(A)$를 만들었다.
$D_0=A_0$이다.
0ドル<i<N$인 $i$에 대해 $D_i=A_{i}-A_{i-1}$이다.
하지만 이 함수를 가지고 놀던 하바는 함수를 여러 번 적용할 수 있다는 것을 깨닫고, 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $B$를 반환하는 함수 $f(A)$를 만들었다.
0ドル\le i<N$인 $i$에 대해 $B_{i}=(d^{i}(A))_i$이다.
$d^i$가 무엇을 의미하는지 모른다면 하단의 노트를 참고하자.
이제 조금 더 재밌는 함수를 가진 하바는 가지고 있던 수열 $A$에 함수 $f$를 $K$번 적용하여 $B=f^{K}(A)$를 만들었다.
수열 $B$와 함수를 적용한 횟수 $K$가 주어질 때 하바가 가지고 있던 수열 $A$를 추정해 보자.
출력
만약 조건을 만족하는 수열 $A$가 존재하지 않는다면 첫째 줄에 -1
만약 조건을 만족하는 수열 $A$가 존재한다면 첫째 줄에 수열 $A$의 각 원소 $A_0,ドル $A_1,ドル $\ldots,ドル $A_{N-1}$을 10ドル^9 + 7$로 나눈 나머지를 공백으로 구분하여 출력한다.
만약 가능한 수열이 여러 가지라면 그중 아무거나 하나를 출력한다.
예제 출력 1
복사
1 4 27 256 3125
$A = [1, 4, 27, 256, 3125]$라고 하자. 그러면 함수를 1ドル$번 적용한 결과는 $f(A) = [1, 3, 20, 186, 2248]$이 되고, 여기에 함수를 1ドル$번 더 적용하면 $B = f(f(A)) = [1, 2, 15, 134, 1613]$이 된다.
노트
어떠한 함수 $f$에 대해 $f^{n}$은 다음과 같이 정의한다.
$f^{0}(X) =X$다.
$f^{n}(X) =f(f^{n-1}(X))$다.
W3sicHJvYmxlbV9pZCI6IjMzNzIzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiW0ZdIEZ1bmN0aW9uYWwgU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1OFx1YmMxNFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YzIxOFx1YzVmNFx1YWNmYyBcdWQ1NjhcdWMyMThcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmMzMFx1YzZlMFx1YjJlNC4gXHViYzMwXHVjNmI0IFx1YWM4M1x1Yzc0NCBcdWJjMTRcdWI4NWMgXHVjODAxXHVjNmE5XHVkNTU4XHViMjk0IFx1YzEzMVx1YWNhOVx1Yzc1OCBcdWQ1NThcdWJjMTRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFlMzhcdWM3NzQgJE4kXHVjNzU4IFx1YzIxOFx1YzVmNCAkQSRcdWI5N2MgXHViYzFiXHVjNTQ0XHVjMTFjIFx1YWUzOFx1Yzc3NCAkTiRcdWM3NTggXHVjMjE4XHVjNWY0ICREJFx1Yjk3YyBcdWJjMThcdWQ2NThcdWQ1NThcdWIyOTQgXHVkNTY4XHVjMjE4ICRkKEEpJFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JERfMD1BXzAkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kMCZsdDtpJmx0O04kXHVjNzc4ICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJERfaT1BX3tpfS1BX3tpLTF9JFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0IFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHViMTgwXHViMzU4IFx1ZDU1OFx1YmMxNFx1YjI5NCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM4MDFcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTY4XHViMmViXHVhY2UwLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWUzOFx1Yzc3NCAkTiRcdWM3NTggXHVjMjE4XHVjNWY0ICRBJFx1Yjk3YyBcdWJjMWJcdWM1NDRcdWMxMWMgXHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWMyMThcdWM1ZjQgJEIkXHViOTdjIFx1YmMxOFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWQ1NjhcdWMyMTggJGYoQSkkXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMFxcbGUgaSZsdDtOJFx1Yzc3OCAkaSRcdWM1ZDAgXHViMzAwXHVkNTc0ICRCX3tpfT0oZF57aX0oQSkpX2kkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiRkXmkkXHVhYzAwIFx1YmIzNFx1YzVjN1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTRcdWM5YzAgXHViYWE4XHViOTc4XHViMmU0XHViYTc0IFx1ZDU1OFx1YjJlOFx1Yzc1OCBcdWIxNzhcdWQyYjhcdWI5N2MgXHVjYzM4XHVhY2UwXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjODcwXHVhZTA4IFx1YjM1NCBcdWM3YWNcdWJjMGNcdWIyOTQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YWMwMFx1YzljNCBcdWQ1NThcdWJjMTRcdWIyOTQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjM1OCBcdWMyMThcdWM1ZjQgJEEkXHVjNWQwIFx1ZDU2OFx1YzIxOCAkZiRcdWI5N2MgJEskXHViYzg4IFx1YzgwMVx1YzZhOVx1ZDU1OFx1YzVlYyAkQj1mXntLfShBKSRcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgJEIkXHVjNjQwIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVkNjlmXHVjMjE4ICRLJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1ZDU1OFx1YmMxNFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMzU4IFx1YzIxOFx1YzVmNCAkQSRcdWI5N2MgXHVjZDk0XHVjODE1XHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU4XHViYzE0XHVhYzAwIFx1YjljY1x1YjRlMCBcdWMyMThcdWM1ZjQgJEIkXHVjNzU4IFx1YWUzOFx1Yzc3NCAkTiRcdWFjZmMgXHVkNTU4XHViYzE0XHVhYzAwIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVkNjlmXHVjMjE4ICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgTiBcXGxlIDVcXCwwMDA7JCAkMCBcXGxlIEsgXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgJEIkXHVjNzU4IFx1YzZkMFx1YzE4YyAkQl8wJCwgJEJfMSQsICRcXGxkb3RzJCwgJEJfe04tMX0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDAgXFxsZSBCX3tpfSBcXGxlIDEwXjkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNCAkQSRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4tMTxcL2NvZGU+PFwvc3Bhbj5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQgJEEkXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCAkQSRcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4YyAkQV8wJCwgJEFfMSQsICRcXGxkb3RzJCwgJEFfe04tMX0kXHVjNzQ0ICQxMF45ICsgNyRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCBcdWFkZjhcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzViNFx1YjVhMFx1ZDU1YyBcdWQ1NjhcdWMyMTggJGYkXHVjNWQwIFx1YjMwMFx1ZDU3NCAkZl57bn0kXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRmXnswfShYKSA9WCRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRmXntufShYKSA9ZihmXntuLTF9KFgpKSRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD4kQSA9IFsxLCA0LCAyNywgMjU2LCAzMTI1XSRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZWNcdWJhNzQgXHVkNTY4XHVjMjE4XHViOTdjICQxJFx1YmM4OCBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViMjk0ICRmKEEpID0gWzEsIDMsIDIwLCAxODYsIDIyNDhdJFx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YzVlY1x1YWUzMFx1YzVkMCBcdWQ1NjhcdWMyMThcdWI5N2MgJDEkXHViYzg4IFx1YjM1NCBcdWM4MDFcdWM2YTlcdWQ1NThcdWJhNzQgJEIgPSBmKGYoQSkpID0gWzEsIDIsIDE1LCAxMzQsIDE2MTNdJFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzM3MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJbRl0gRnVuY3Rpb25hbCBTZXF1ZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+SEIgaGFzIHJlY2VudGx5IGxlYXJuZWQgYWJvdXQgZnVuY3Rpb25zIGFuZCBzZXF1ZW5jZXMgYXQgc2Nob29sLiBIQiBsaWtlcyB0byBhcHBseSBuZXcga25vd2xlZGdlIGltbWVkaWF0ZWx5IHNvIGhlIGhhcyBjcmVhdGVkIHRoZSBmdW5jdGlvbiAkZChBKSQgd2hpY2ggdGFrZXMgYSBzZXF1ZW5jZSAkQSQgb2YgbGVuZ3RoICROJCBhbmQgcmV0dXJucyBhIHNlcXVlbmNlICREJCBvZiBsZW5ndGggJE4kLiBUaGlzIGZ1bmN0aW9uJm5ic3A7aXMgZGVmaW5lZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiREXzA9QV8wJC48XC9saT5cclxuXHQ8bGk+Rm9yIGFsbCAkaSQgc3VjaCB0aGF0ICQwJmx0O2kmbHQ7TiQsICREX2k9QV97aX0tQV97aS0xfSQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V2hpbGUgcGxheWluZyB3aXRoIGhpcyBuZXcgZnVuY3Rpb24sIEhCIGhhcyByZWFsaXplZCB0aGF0IHlvdSBjYW4gYXBwbHkgdGhpcyBmdW5jdGlvbiBtdWx0aXBsZSB0aW1lcyB0byBjcmVhdGUgYSBuZXcgZnVuY3Rpb24gJGYoQSkkJm5ic3A7d2hpY2gmbmJzcDt0YWtlcyBhIHNlcXVlbmNlICRBJCBvZiBsZW5ndGggJE4kIGFuZCByZXR1cm5zIGEgc2VxdWVuY2UgJEIkIG9mIGxlbmd0aCAkTiQuIFRoaXMgZnVuY3Rpb24gaXMgZGVmaW5lZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkZvciBhbGwgJGkkIHN1Y2ggdGhhdCAkMFxcbGUgaSZsdDtOJCwgJEJfe2l9PShkXntpfShBKSlfaSQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgeW91IGFyZSB1bmZhbWlsaWFyIHdpdGgmbmJzcDt3aGF0ICRkXmkkIG1lYW5zLCByZWZlciB0byB0aGUgbm90ZSBzZWN0aW9uIGJlbG93LjxcL3A+XHJcblxyXG48cD5Ob3cgdGhhdCBIQiBoYXMgYSBtb3JlIGludGVyZXN0aW5nIGZ1bmN0aW9uLCBoZSBoYXMgZGVjaWRlZCB0byBtYWtlIGFwcGx5ICRmJCB0byBoaXMgaW5pdGlhbCBzZXF1ZW5jZSAkQSQgbm90IG9uY2UgYnV0ICRLJCB0aW1lcyB0byBtYWtlICRCPWZee0t9KEEpJC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gJEIkIGFuZCAkSyQsIGxldCZyc3F1bztzIGZpbmQgSEImcnNxdW87cyBpbml0aWFsIHNlcXVlbmNlICRBJC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kIGFuZCAkSyQsIGRlbm90aW5nIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlICRCJCB3aGljaCBIQiBoYXMgY3JlYXRlZCwgYW5kIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIGZ1bmN0aW9uIHdhcyBhcHBsaWVkLCByZXNwZWN0aXZlbHkuICQoMSBcXGxlIE4gXFxsZSA1XFwsMDAwOyQgJDAgXFxsZSBLIFxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPnRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyAkQl8wJCwgJEJfMSQsICRcXGxkb3RzJCwgJEJfe04tMX0kLCBkZW5vdGluZyB0aGUgZWxlbWVudHMgb2YgJEIkLiBUaGVyZSBpcyBhIHNwYWNlIGJldHdlZW4gdHdvIGVsZW1lbnRzLiAkKDAgXFxsZSBCX3tpfSBcXGxlIDEwXjkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZXJlIGlzIG5vIHNlcXVlbmNlICRBJCB3aGljaCBzdWl0cyB0aGUgY29uZGl0aW9ucyBnaXZlbiwgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPi0xPFwvY29kZT48XC9zcGFuPiZuYnNwO2luIHRoZSBmaXJzdCBsaW5lLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBleGlzdHMgYSB2YWxpZCBzZXF1ZW5jZSAkQSQsIHByaW50ICRBXzAkLCAkQV8xJCwgJFxcbGRvdHMkLCAkQV97Ti0xfSQsIGRlbm90aW5nIHRoZSBlbGVtZW50cyBvZiAkQSQuIFByaW50IGVhY2ggZWxlbWVudCBtb2R1bG8gJDEwXjkgKyA3JCB3aXRoIGEgc3BhY2UgYmV0d2VlbiB0d28gZWxlbWVudHMuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBtdWx0aXBsZSB2YWxpZCBzZXF1ZW5jZXMsIHByaW50IGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiPHA+Rm9yIGEgZnVuY3Rpb24gJGYkLCAkZl57bn0kIGlzIGRlZmluZWQgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kZl57MH0oWCkgPVgkLjxcL2xpPlxyXG5cdDxsaT4kZl57bn0oWCkgPWYoZl57bi0xfShYKSkkLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkxldCYjMzk7cyBzYXkgJEEgPSBbMSwgNCwgMjcsIDI1NiwgMzEyNV0kLiBBcHBseWluZyB0aGUgZnVuY3Rpb24gJDEkIHRpbWUgcmVzdWx0cyBpbiAkZihBKSA9IFsxLCAzLCAyMCwgMTg2LCAyMjQ4XSQsIGFuZCBhcHBseWluZyB0aGUgZnVuY3Rpb24gJDEkIG1vcmUgdGltZSByZXN1bHRzIGluICRCID0gZihmKEEpKSA9IFsxLCAyLCAxNSwgMTM0LCAxNjEzXSQuPFwvcD5cclxuIn1d