시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1094 222 136 21.519%

문제

상근이는 시간이 날 때마다 색칠 공부를 하고 있다. 상근이는 총 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGM5XHVjZTYwIFx1YWNmNVx1YmQ4MCBcdWNjNDVcdWM3NDQgXHVjMGM5XHVjZTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWJjODggXHVhZGY4XHViOWJjXHVhY2ZjIDJcdWJjODggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1YzBjOVx1Y2U2MFx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0MCAoMSwyKSwgKDEsMyksICgyLDEpLCAoMiwzKSwgKDMsMSksICgzLDIpXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1MjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQQUxFVEEiLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBNaXJrbyBzcGVuZHMgaGlzIGZyZWUgdGltZSBwYWludGluZy4gRm9yIHRoaXMgaG9iYnksIGhlIGxpa2VzIHRvIHVzZSBicnVzaGVzIGFuZCBhIHBhbGxldCBjb250YWluaW5nIEsgY29sb3JzIG92ZXJhbGwuIEhpcyBmcmllbmQgU2xhdmtvIGRlY2lkZWQgdG8gdXNlIE1pcmtvJiMzOTtzIHRhbGVudCBhbmQgZ2F2ZSBoaW0gaGlzIG5ldyBjb2xvcmluZyBib29rIGZvciBNaXJrbyB0byBjb2xvci4gVGhlIGNvbG9yaW5nIGJvb2sgY29udGFpbnMgTiBpbWFnZXMgbnVtYmVyZWQgMSwgMiwgLi4uLCBOLiZuYnNwOzxiciBcLz5cclxuJm5ic3A7PGJyIFwvPlxyXG5NaXJrbyBoYXMgZGVjaWRlZCB0byBwYWludCBlYWNoIGltYWdlIGluIGV4YWN0bHkgb25lIGNvbG9yIG9mIHRoZSBwb3NzaWJsZSBLIGNvbG9ycyBmcm9tIGhpcyBwYWxsZXQuIEhvd2V2ZXIsIGhlIHJlYWxseSBsaWtlcyBjb2xvcmZ1bCB0aGluZ3MuIEhlIGNob3NlIE4gbnVtYmVycyBmPHN1Yj5pPFwvc3ViPiBhbmQgZGVjaWRlZCB0byBwYWludCB0aGUgaW1hZ2UgbnVtYmVyZWQgaSBkaWZmZXJlbnRseSB0aGFuIHRoZSBpbWFnZXMgbnVtYmVyZWQgZjxzdWI+aTxcL3N1Yj4sIGV4Y2VwdCB3aGVuIGY8c3ViPmk8XC9zdWI+ID0gaS4gSWYgZjxzdWI+aTxcL3N1Yj4gPSBpLCB0aGF0IG1lYW5zIGhlIGNhbiBwYWludCB0aGUgaW1hZ2UgbnVtYmVyZWQgZjxzdWI+aTxcL3N1Yj4gd2hpY2hldmVyIGNvbG9yIGhlIGxpa2VzLCBhcyBsb25nIGFzIGFsbCBvdGhlciBjb25kaXRpb25zIGhhdmUgYmVlbiBtZXQuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbk1pcmtvIHdhbnRzIHRvIGtub3cgdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIHRvIGNvbG9yIFNsYXZrbyYjMzk7cyBjb2xvcmluZyBib29rIGFuZCBoZSBkZXNwZXJhdGVseSBuZWVkcyB5b3VyIGhlbHAhIENhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgdG8gY29sb3IgdGhlIGJvb2suIEdpdmVuIHRoZSBmYWN0IHRoYXQgdGhlIG91dHB1dCBjYW4gYmUgdmVyeSBsYXJnZSwgcHJpbnQgdGhlIGFuc3dlciBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHBvc2l0aXZlIGludGVnZXJzIE4sIEsgKDEgJmxlOyBOLCBLICZsZTsgMSAwMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIGxpbmUgY29udGFpbnMgTiBudW1iZXJzIGY8c3ViPmk8XC9zdWI+ICgxICZsZTsgZjxzdWI+aTxcL3N1Yj4gJmxlOyBOKSwgdGhlIG51bWJlciBzdGF0ZWQgaW4gdGhlIHRleHQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgbXVzdCBjb250YWluIHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBjb2xvciBTbGF2a28mIzM5O3MgYm9vay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+TWlya28gaGFzIHRocmVlIGNvbG9ycyBhbmQgZGVjaWRlZCB0aGF0IHRoZSBpbWFnZSBudW1iZXJlZCAyIG11c3RuJiMzOTt0IGJlIG9mIHRoZSBzYW1lIGNvbG9yIGFzIHRoZSBpbWFnZSBudW1iZXJlZCAxLiBUaGUgcG9zc2libGUgY29sb3JpbmdzIGFyZSAoMSwgMiksICgxLCAzKSwgKDIsIDEpLCAoMiwgMyksICgzLCAxKSwgKDMsIDIpLCB3aGVyZSB0aGUgZmlyc3QgbnVtYmVyIGluIHRoZSBicmFja2V0cyByZXByZXNlbnRzIHRoZSBjb2xvciBvZiB0aGUgZmlyc3QgaW1hZ2UgYW5kIHRoZSBzZWNvbmQgbnVtYmVyIHRoZSBjb2xvciBvZiB0aGUgc2Vjb25kIGltYWdlLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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