시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 754 155 97 23.892%

문제

상근이는 시간이 날 때마다 색칠 공부를 하고 있다. 상근이는 총 K개의 색이 담겨있는 팔레트를 가지고 있고, 붓을 이용해 색칠을 한다. 상근이의 친구 선영이는 상근이의 생일 선물로 색칠 공부 책을 선물했다. 책에는 그림이 총 N개 있으며, 1번부터 N번까지 번호가 붙여져 있다.

상근이는 각각의 그림을 K가지 색 중 하나를 골라 색칠하려고 한다. 선영이는 화려한 것을 좋아하기 때문에 상근이에게 숫자 N개 fi를 정해주었다. 상근이는 i번 그림을 fi번 그림과 다른 색으로 색칠해야 한다. i가 fi와 같은 경우에 아무런 제한없이 i번 그림을 색칠할 수 있다.

N과 K, 그리고 fi가 모두 주어졌을 때, 상근이가 색칠 공부 책을 색칠하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 1,000,000) 둘째 줄에는 숫자 N개 fi가 주어진다. (1 ≤ fi ≤ N)

출력

첫째 줄에 색칠 공부 책을 색칠하는 방법의 수를 출력한다. 방법의 수가 매우 많기 때문에 1,000,000,007로 나눈 나머지를 출력한다. 

예제 입력 1

2 3
2 1

예제 출력 1

6

힌트

1번 그림과 2번 그림은 서로 같은 색으로 색칠하면 안된다. 따라서 가능한 방법은 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)가 있다.

W3sicHJvYmxlbV9pZCI6Ijk1MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzlcdWNlNjAgXHVhY2Y1XHViZDgwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjBhMCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDFkIEtcdWFjMWNcdWM3NTggXHVjMGM5XHVjNzc0IFx1YjJmNFx1YWNhOFx1Yzc4OFx1YjI5NCBcdWQzMTRcdWI4MDhcdWQyYjhcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHViZDkzXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMwYzlcdWNlNjBcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMGRkXHVjNzdjIFx1YzEyMFx1YmIzY1x1Yjg1YyBcdWMwYzlcdWNlNjAgXHVhY2Y1XHViZDgwIFx1Y2M0NVx1Yzc0NCBcdWMxMjBcdWJiM2NcdWQ1ODhcdWIyZTQuIFx1Y2M0NVx1YzVkMFx1YjI5NCBcdWFkZjhcdWI5YmNcdWM3NzQgXHVjZDFkIE5cdWFjMWMgXHVjNzg4XHVjNzNjXHViYTcwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQ0IEtcdWFjMDBcdWM5YzAgXHVjMGM5IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWI4MjRcdWQ1NWMgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzIyYlx1Yzc5MCBOXHVhYzFjIGY8c3ViPmk8XC9zdWI+XHViOTdjIFx1YzgxNVx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IGlcdWJjODggXHVhZGY4XHViOWJjXHVjNzQ0IGY8c3ViPmk8XC9zdWI+XHViYzg4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWIyZTRcdWI5NzggXHVjMGM5XHVjNzNjXHViODVjIFx1YzBjOVx1Y2U2MFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIGlcdWFjMDAgZjxzdWI+aTxcL3N1Yj5cdWM2NDAmbmJzcDtcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1YmIzNFx1YjdmMCBcdWM4MWNcdWQ1NWNcdWM1YzZcdWM3NzQgaVx1YmM4OCBcdWFkZjhcdWI5YmNcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgSywgXHVhZGY4XHViOWFjXHVhY2UwIGY8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MCBcdWNjNDVcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgSyAmbGU7IDEsMDAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTAgTlx1YWMxYyBmPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgZjxzdWI+aTxcL3N1Yj4gJmxlOyBOKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MCBcdWNjNDVcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWJjODggXHVhZGY4XHViOWJjXHVhY2ZjIDJcdWJjODggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzQwICgxLDIpLCAoMSwzKSwgKDIsMSksICgyLDMpLCAoMywxKSwgKDMsMilcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTUyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBBTEVUQSIsImRlc2NyaXB0aW9uIjoiPHA+TGl0dGxlIE1pcmtvIHNwZW5kcyBoaXMgZnJlZSB0aW1lIHBhaW50aW5nLiBGb3IgdGhpcyBob2JieSwgaGUgbGlrZXMgdG8gdXNlIGJydXNoZXMgYW5kIGEgcGFsbGV0IGNvbnRhaW5pbmcgSyBjb2xvcnMgb3ZlcmFsbC4gSGlzIGZyaWVuZCBTbGF2a28gZGVjaWRlZCB0byB1c2UgTWlya28mIzM5O3MgdGFsZW50IGFuZCBnYXZlIGhpbSBoaXMgbmV3IGNvbG9yaW5nIGJvb2sgZm9yIE1pcmtvIHRvIGNvbG9yLiBUaGUgY29sb3JpbmcgYm9vayBjb250YWlucyBOIGltYWdlcyBudW1iZXJlZCAxLCAyLCAuLi4sIE4uJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbk1pcmtvIGhhcyBkZWNpZGVkIHRvIHBhaW50IGVhY2ggaW1hZ2UgaW4gZXhhY3RseSBvbmUgY29sb3Igb2YgdGhlIHBvc3NpYmxlIEsgY29sb3JzIGZyb20gaGlzIHBhbGxldC4gSG93ZXZlciwgaGUgcmVhbGx5IGxpa2VzIGNvbG9yZnVsIHRoaW5ncy4gSGUgY2hvc2UgTiBudW1iZXJzIGY8c3ViPmk8XC9zdWI+IGFuZCBkZWNpZGVkIHRvIHBhaW50IHRoZSBpbWFnZSBudW1iZXJlZCBpIGRpZmZlcmVudGx5IHRoYW4gdGhlIGltYWdlcyBudW1iZXJlZCBmPHN1Yj5pPFwvc3ViPiwgZXhjZXB0IHdoZW4gZjxzdWI+aTxcL3N1Yj4gPSBpLiBJZiBmPHN1Yj5pPFwvc3ViPiA9IGksIHRoYXQgbWVhbnMgaGUgY2FuIHBhaW50IHRoZSBpbWFnZSBudW1iZXJlZCBmPHN1Yj5pPFwvc3ViPiB3aGljaGV2ZXIgY29sb3IgaGUgbGlrZXMsIGFzIGxvbmcgYXMgYWxsIG90aGVyIGNvbmRpdGlvbnMgaGF2ZSBiZWVuIG1ldC4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuTWlya28gd2FudHMgdG8ga25vdyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgdG8gY29sb3IgU2xhdmtvJiMzOTtzIGNvbG9yaW5nIGJvb2sgYW5kIGhlIGRlc3BlcmF0ZWx5IG5lZWRzIHlvdXIgaGVscCEgQ2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBjb2xvciB0aGUgYm9vay4gR2l2ZW4gdGhlIGZhY3QgdGhhdCB0aGUgb3V0cHV0IGNhbiBiZSB2ZXJ5IGxhcmdlLCBwcmludCB0aGUgYW5zd2VyIG1vZHVsbyAxIDAwMCAwMDAgMDA3LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgcG9zaXRpdmUgaW50ZWdlcnMgTiwgSyAoMSAmbGU7IE4sIEsgJmxlOyAxIDAwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgbGluZSBjb250YWlucyBOIG51bWJlcnMgZjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBmPHN1Yj5pPFwvc3ViPiAmbGU7IE4pLCB0aGUgbnVtYmVyIHN0YXRlZCBpbiB0aGUgdGV4dC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBtdXN0IGNvbnRhaW4gdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIHRvIGNvbG9yIFNsYXZrbyYjMzk7cyBib29rLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5NaXJrbyBoYXMgdGhyZWUgY29sb3JzIGFuZCBkZWNpZGVkIHRoYXQgdGhlIGltYWdlIG51bWJlcmVkIDIgbXVzdG4mIzM5O3QgYmUgb2YgdGhlIHNhbWUgY29sb3IgYXMgdGhlIGltYWdlIG51bWJlcmVkIDEuIFRoZSBwb3NzaWJsZSBjb2xvcmluZ3MgYXJlICgxLCAyKSwgKDEsIDMpLCAoMiwgMSksICgyLCAzKSwgKDMsIDEpLCAoMywgMiksIHdoZXJlIHRoZSBmaXJzdCBudW1iZXIgaW4gdGhlIGJyYWNrZXRzIHJlcHJlc2VudHMgdGhlIGNvbG9yIG9mIHRoZSBmaXJzdCBpbWFnZSBhbmQgdGhlIHNlY29uZCBudW1iZXIgdGhlIGNvbG9yIG9mIHRoZSBzZWNvbmQgaW1hZ2UuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #2 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: uk7880