시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB161331320919.478%

문제

상근이는 시간이 날 때마다 색칠 공부를 하고 있다. 상근이는 총 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

예제 입력 2

3 4
2 3 1

예제 출력 2

24

예제 입력 3

3 4
2 1 1

예제 출력 3

36

예제 입력 4

3 4
1 1 2

예제 출력 4

36

힌트

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

W3sicHJvYmxlbV9pZCI6Ijk1MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzlcdWNlNjAgXHVhY2Y1XHViZDgwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjBhMCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDFkIEtcdWFjMWNcdWM3NTggXHVjMGM5XHVjNzc0IFx1YjJmNFx1YWNhOFx1Yzc4OFx1YjI5NCBcdWQzMTRcdWI4MDhcdWQyYjhcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHViZDkzXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMwYzlcdWNlNjBcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMGRkXHVjNzdjIFx1YzEyMFx1YmIzY1x1Yjg1YyBcdWMwYzlcdWNlNjAgXHVhY2Y1XHViZDgwIFx1Y2M0NVx1Yzc0NCBcdWMxMjBcdWJiM2NcdWQ1ODhcdWIyZTQuIFx1Y2M0NVx1YzVkMFx1YjI5NCBcdWFkZjhcdWI5YmNcdWM3NzQgXHVjZDFkIE5cdWFjMWMgXHVjNzg4XHVjNzNjXHViYTcwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQ0IEtcdWFjMDBcdWM5YzAgXHVjMGM5IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWI4MjRcdWQ1NWMgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzIyYlx1Yzc5MCBOXHVhYzFjIGY8c3ViPmk8XC9zdWI+XHViOTdjIFx1YzgxNVx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IGlcdWJjODggXHVhZGY4XHViOWJjXHVjNzQ0IGY8c3ViPmk8XC9zdWI+XHViYzg4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWIyZTRcdWI5NzggXHVjMGM5XHVjNzNjXHViODVjIFx1YzBjOVx1Y2U2MFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIGlcdWFjMDAgZjxzdWI+aTxcL3N1Yj5cdWM2NDAmbmJzcDtcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1YmIzNFx1YjdmMCBcdWM4MWNcdWQ1NWNcdWM1YzZcdWM3NzQgaVx1YmM4OCBcdWFkZjhcdWI5YmNcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgSywgXHVhZGY4XHViOWFjXHVhY2UwIGY8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MCBcdWNjNDVcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgSyAmbGU7IDEsMDAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTAgTlx1YWMxYyBmPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgZjxzdWI+aTxcL3N1Yj4gJmxlOyBOKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MCBcdWNjNDVcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCAxXHViYzg4IFx1YWRmOFx1YjliY1x1YWNmYyAyXHViYzg4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWMxMWNcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YzBjOVx1YzczY1x1Yjg1YyBcdWMwYzlcdWNlNjBcdWQ1NThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDAgKDEsMiksICgxLDMpLCAoMiwxKSwgKDIsMyksICgzLDEpLCAoMywyKVx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NTIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEFMRVRBIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgTWlya28gc3BlbmRzIGhpcyBmcmVlIHRpbWUgcGFpbnRpbmcuIEZvciB0aGlzIGhvYmJ5LCBoZSBsaWtlcyB0byB1c2UgYnJ1c2hlcyBhbmQgYSBwYWxsZXQgY29udGFpbmluZyBLIGNvbG9ycyBvdmVyYWxsLiBIaXMgZnJpZW5kIFNsYXZrbyBkZWNpZGVkIHRvIHVzZSBNaXJrbyYjMzk7cyB0YWxlbnQgYW5kIGdhdmUgaGltIGhpcyBuZXcgY29sb3JpbmcgYm9vayBmb3IgTWlya28gdG8gY29sb3IuIFRoZSBjb2xvcmluZyBib29rIGNvbnRhaW5zIE4gaW1hZ2VzIG51bWJlcmVkIDEsIDIsIC4uLiwgTi4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuTWlya28gaGFzIGRlY2lkZWQgdG8gcGFpbnQgZWFjaCBpbWFnZSBpbiBleGFjdGx5IG9uZSBjb2xvciBvZiB0aGUgcG9zc2libGUgSyBjb2xvcnMgZnJvbSBoaXMgcGFsbGV0LiBIb3dldmVyLCBoZSByZWFsbHkgbGlrZXMgY29sb3JmdWwgdGhpbmdzLiBIZSBjaG9zZSBOIG51bWJlcnMgZjxzdWI+aTxcL3N1Yj4gYW5kIGRlY2lkZWQgdG8gcGFpbnQgdGhlIGltYWdlIG51bWJlcmVkIGkgZGlmZmVyZW50bHkgdGhhbiB0aGUgaW1hZ2VzIG51bWJlcmVkIGY8c3ViPmk8XC9zdWI+LCBleGNlcHQgd2hlbiBmPHN1Yj5pPFwvc3ViPiA9IGkuIElmIGY8c3ViPmk8XC9zdWI+ID0gaSwgdGhhdCBtZWFucyBoZSBjYW4gcGFpbnQgdGhlIGltYWdlIG51bWJlcmVkIGY8c3ViPmk8XC9zdWI+IHdoaWNoZXZlciBjb2xvciBoZSBsaWtlcywgYXMgbG9uZyBhcyBhbGwgb3RoZXIgY29uZGl0aW9ucyBoYXZlIGJlZW4gbWV0LiZuYnNwOzxiciBcLz5cclxuJm5ic3A7PGJyIFwvPlxyXG5NaXJrbyB3YW50cyB0byBrbm93IHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBjb2xvciBTbGF2a28mIzM5O3MgY29sb3JpbmcgYm9vayBhbmQgaGUgZGVzcGVyYXRlbHkgbmVlZHMgeW91ciBoZWxwISBDYWxjdWxhdGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIHRvIGNvbG9yIHRoZSBib29rLiBHaXZlbiB0aGUgZmFjdCB0aGF0IHRoZSBvdXRwdXQgY2FuIGJlIHZlcnkgbGFyZ2UsIHByaW50IHRoZSBhbnN3ZXIgbW9kdWxvIDEgMDAwIDAwMCAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBwb3NpdGl2ZSBpbnRlZ2VycyBOLCBLICgxICZsZTsgTiwgSyAmbGU7IDEgMDAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIE4gbnVtYmVycyBmPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGY8c3ViPmk8XC9zdWI+ICZsZTsgTiksIHRoZSBudW1iZXIgc3RhdGVkIGluIHRoZSB0ZXh0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgdG8gY29sb3IgU2xhdmtvJiMzOTtzIGJvb2suJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIGZpcnN0IGV4YW1wbGU6IE1pcmtvIGhhcyB0aHJlZSBjb2xvcnMgYW5kIGRlY2lkZWQgdGhhdCB0aGUgaW1hZ2UgbnVtYmVyZWQgMiBtdXN0biYjMzk7dCBiZSBvZiB0aGUgc2FtZSBjb2xvciBhcyB0aGUgaW1hZ2UgbnVtYmVyZWQgMS4gVGhlIHBvc3NpYmxlIGNvbG9yaW5ncyBhcmUgKDEsIDIpLCAoMSwgMyksICgyLCAxKSwgKDIsIDMpLCAoMywgMSksICgzLCAyKSwgd2hlcmUgdGhlIGZpcnN0IG51bWJlciBpbiB0aGUgYnJhY2tldHMgcmVwcmVzZW50cyB0aGUgY29sb3Igb2YgdGhlIGZpcnN0IGltYWdlIGFuZCB0aGUgc2Vjb25kIG51bWJlciB0aGUgY29sb3Igb2YgdGhlIHNlY29uZCBpbWFnZS48XC9wPlxyXG5cclxuPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZm91cnRoIGV4YW1wbGU6IE1pcmtvIGhhcyBmb3VyIGNvbG9ycy4gVGhlcmUgYXJlIG5vIGNvbmRpdGlvbnMgcmVnYXJkaW5nIHRoZSBmaXJzdCBpbWFnZSwgaXQgY2FuIGJlIHBhaW50ZWQgaW4gd2hpY2hldmVyIGNvbG9yLiBUaGUgc2Vjb25kIG11c3QgYmUgZGlmZmVyZW50IHRoYW4gdGhlIGZpcnN0LCBhbmQgdGhlIHRoaXJkIGRpZmZlcmVudCB0aGFuIHRoZSBzZWNvbmQuIFRoYXQgbWVhbnMgdGhhdCB0aG9zZSB0d28gaW1hZ2VzIGNhbiBiZSBjb2xvcmVkIGluIHRoZSByZW1haW5pbmcgMyBjb2xvcnMuIFRoaXMgZ2l2ZXMgdXMgYSB0b3RhbCBvZiAzNiBjb21iaW5hdGlvbnMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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

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