31070번 - 라면 배달하기 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB120646061.224%

문제

서울과학고의 기숙사는 $N$개의 방과 서로 다른 두 방을 연결하는 $N-1$개의 복도로 이루어진 트리 형태로 표현할 수 있다. 모든 복도는 양방향으로 이동할 수 있고, 복도를 이용해 모든 방 사이를 이동할 수 있다. 하나의 복도를 통과하는 데 걸리는 시간은 $1$이다.

민규는 $K$명의 친구에게 컵라면을 끓여주려고 한다. 현재 민규는 $1$번 방에 있으며, 민규를 포함한 모든 친구들은 서로 다른 방에 있다.

이를 위해 민규는 모든 친구들에게 뜨거운 물을 전달할 것이다. 뜨거운 물은 민규가 있는 $1$번 방의 정수기에서만 얻을 수 있다. 또한, 민규는 매우 큰 보온병을 가지고 있어 물을 한 번만 받아도 모든 친구에게 줄 수 있는 충분한 양의 물을 받을 수 있다.

라면을 끓이는 행동은 위험한 행동이다. 사감 선생님께 걸리면 벌점을 받을 수 있기 때문이다. 민규는 위험을 최대한 줄이기 위해 가장 마지막으로 뜨거운 물을 배달한 시각이 최대한 빠른 방법으로 $K$개의 방을 방문할 것이다.

민규가 $K$개의 방을 방문하는 방법을 더 자세히 설명하면 다음과 같다.

  • 민규는 물을 받기 전, $K$명의 친구들이 있는 방을 미리 확인한다.
  • 민규는 시각 $0$에 $1$번 방에서 물을 받고 출발해, 가장 마지막으로 뜨거운 물을 배달하는 친구에게 걸리는 시간을 최소화하는 방법으로 $K$개의 방을 방문할 것이다.
  • 시간을 계산할 때는 민규가 복도를 이동하는 시간만 고려한다. 친구에게 물을 주는 시간이나 정수기에서 물을 뜨는 시간 등은 무시한다. 민규가 물을 다 주고 자신의 방으로 돌아가는 시간 역시 무시한다.

민규는 친구들이 있는 방을 확인하기 전에, 친구들에게 물을 배달하는 데 시간이 얼마나 걸릴지 예측하려고 한다. $K$명의 친구들이 있는 방을 고르는 $\binom{N-1}{K}$가지 경우에 대해, 마지막으로 물을 배달하는 시각의 합을 구해 주자.

입력

첫째 줄에 방의 수 $N$과 친구의 수 $K$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$번째 줄까지 $i+1$번째 줄에는 $i$번 복도가 연결하는 두 방의 번호 $U_i$와 $V_i$가 공백으로 구분되어 주어진다.

출력

친구들이 있는 방을 고르는 $\binom{N-1}{K}$가지 경우에 대해 마지막으로 물을 배달하는 시각의 합을 $10^9 + 7$으로 나눈 나머지를 출력하여라.

제한

  • $2\le N\le 10^5$
  • $1\le K\le N-1$
  • $1\le U_i\le N$ $(1\le i<N)$
  • $1\le V_i\le N$ $(1\le i<N)$
  • $U_i\ne V_i$ $(1\le i<N)$
  • 입력으로 주어지는 서울과학고의 구조는 트리임이 보장된다.

서브태스크

번호배점제한
110

$N \le 10$

240

$N \le 10^3$

350

추가 제한 조건이 없다.

예제 입력 1 

4 2
1 2
2 3
1 4

예제 출력 1 

9

예제 입력 2 

7 6
1 2
2 3
2 4
4 5
4 6
1 7

예제 출력 2 

9

예제 입력 3 

10 5
1 2
2 3
2 4
4 5
4 6
5 7
1 8
8 9
8 10

예제 출력 3 

1210
W3sicHJvYmxlbV9pZCI6IjMxMDcwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNzdjXHViYTc0IFx1YmMzMFx1YjJlY1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMTFjXHVjNmI4XHVhY2ZjXHVkNTU5XHVhY2UwXHVjNzU4IFx1YWUzMFx1YzIxOVx1YzBhY1x1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHViYzI5XHVhY2ZjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YmMyOVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgJE4tMSRcdWFjMWNcdWM3NTggXHViY2Y1XHViM2M0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWMgXHVkNjE1XHVkMGRjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViY2Y1XHViM2M0XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViY2Y1XHViM2M0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWJhYThcdWI0ZTAgXHViYzI5IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1YmNmNVx1YjNjNFx1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgJDEkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZmNcdWFkZGNcdWIyOTQgJEskXHViYTg1XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWNlZjVcdWI3N2NcdWJhNzRcdWM3NDQgXHViMDUzXHVjNWVjXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YmJmY1x1YWRkY1x1YjI5NCAkMSRcdWJjODggXHViYzI5XHVjNWQwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViYmZjXHVhZGRjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYzI5XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWJiZmNcdWFkZGNcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWI3MjhcdWFjNzBcdWM2YjQgXHViYjNjXHVjNzQ0IFx1YzgwNFx1YjJlY1x1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjcyOFx1YWM3MFx1YzZiNCBcdWJiM2NcdWM3NDAgXHViYmZjXHVhZGRjXHVhYzAwIFx1Yzc4OFx1YjI5NCAkMSRcdWJjODggXHViYzI5XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWUzMFx1YzVkMFx1YzExY1x1YjljYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWJiZmNcdWFkZGNcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3MCBcdWJjZjRcdWM2MjhcdWJjZDFcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzViNCBcdWJiM2NcdWM3NDQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWJjMWJcdWM1NDRcdWIzYzQgXHViYWE4XHViNGUwIFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkYTlcdWJkODRcdWQ1NWMgXHVjNTkxXHVjNzU4IFx1YmIzY1x1Yzc0NCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzdjXHViYTc0XHVjNzQ0IFx1YjA1M1x1Yzc3NFx1YjI5NCBcdWQ1ODlcdWIzZDlcdWM3NDAgXHVjNzA0XHVkNWQ4XHVkNTVjIFx1ZDU4OVx1YjNkOVx1Yzc3NFx1YjJlNC4gXHVjMGFjXHVhYzEwIFx1YzEyMFx1YzBkZFx1YjJkOFx1YWVkOCBcdWFjNzhcdWI5YWNcdWJhNzQgXHViYzhjXHVjODEwXHVjNzQ0IFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViYmZjXHVhZGRjXHViMjk0IFx1YzcwNFx1ZDVkOFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjOTA0XHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YjcyOFx1YWM3MFx1YzZiNCBcdWJiM2NcdWM3NDQgXHViYzMwXHViMmVjXHVkNTVjIFx1YzJkY1x1YWMwMVx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViZTYwXHViOTc4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyAkSyRcdWFjMWNcdWM3NTggXHViYzI5XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmJmY1x1YWRkY1x1YWMwMCAkSyRcdWFjMWNcdWM3NTggXHViYzI5XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHViMzU0IFx1Yzc5MFx1YzEzOFx1ZDc4OCBcdWMxMjRcdWJhODVcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJiZmNcdWFkZGNcdWIyOTQgXHViYjNjXHVjNzQ0IFx1YmMxYlx1YWUzMCBcdWM4MDQsICRLJFx1YmE4NVx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc0NCBcdWJiZjhcdWI5YWMgXHVkNjU1XHVjNzc4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJiZmNcdWFkZGNcdWIyOTQgXHVjMmRjXHVhYzAxICQwJFx1YzVkMCAkMSRcdWJjODggXHViYzI5XHVjNWQwXHVjMTFjIFx1YmIzY1x1Yzc0NCBcdWJjMWJcdWFjZTAgXHVjZDljXHViYzFjXHVkNTc0LCBcdWFjMDBcdWM3YTUgXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YjcyOFx1YWM3MFx1YzZiNCBcdWJiM2NcdWM3NDQgXHViYzMwXHViMmVjXHVkNTU4XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgJEskXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWFjMDRcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWJiZmNcdWFkZGNcdWFjMDAgXHViY2Y1XHViM2M0XHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWI5Y2MgXHVhY2UwXHViODI0XHVkNTVjXHViMmU0LiBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHViYjNjXHVjNzQ0IFx1YzhmY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIwOTggXHVjODE1XHVjMjE4XHVhZTMwXHVjNWQwXHVjMTFjIFx1YmIzY1x1Yzc0NCBcdWI3MjhcdWIyOTQgXHVjMmRjXHVhYzA0IFx1YjRmMVx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuIDxzdHJvbmc+XHViYmZjXHVhZGRjXHVhYzAwIFx1YmIzY1x1Yzc0NCBcdWIyZTQgXHVjOGZjXHVhY2UwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHViMjk0IFx1YzJkY1x1YWMwNCBcdWM1ZWRcdWMyZGMgXHViYjM0XHVjMmRjXHVkNTVjXHViMmU0LjxcL3N0cm9uZz48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJiZmNcdWFkZGNcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVjZTVjXHVhZDZjXHViNGU0XHVjNWQwXHVhYzhjIFx1YmIzY1x1Yzc0NCBcdWJjMzBcdWIyZWNcdWQ1NThcdWIyOTQgXHViMzcwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM1YmNcdWI5YzhcdWIwOTggXHVhYzc4XHViOWI0XHVjOWMwIFx1YzYwOFx1Y2UyMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuICRLJFx1YmE4NVx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgJFxcYmlub217Ti0xfXtLfSRcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YmIzY1x1Yzc0NCBcdWJjMzBcdWIyZWNcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzAxXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NzQgXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMjlcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWNlNWNcdWFkNmNcdWM3NTggXHVjMjE4ICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwICRpKzEkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODggXHViY2Y1XHViM2M0XHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViYzI5XHVjNzU4IFx1YmM4OFx1ZDYzOCAkVV9pJFx1YzY0MCAkVl9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgJFxcYmlub217Ti0xfXtLfSRcdWFjMDBcdWM5YzAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViYjNjXHVjNzQ0IFx1YmMzMFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDFcdWM3NTggXHVkNTY5XHVjNzQ0ICQxMF45ICsgNyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyXFxsZSBOXFxsZSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgS1xcbGUgTi0xJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgVV9pXFxsZSBOJCAkKDFcXGxlIGkmbHQ7TikkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBWX2lcXGxlIE4kICQoMVxcbGUgaSZsdDtOKSQ8XC9saT5cclxuXHQ8bGk+JFVfaVxcbmUgVl9pJCAkKDFcXGxlIGkmbHQ7TikkPFwvbGk+XHJcblx0PGxpPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMTFjXHVjNmI4XHVhY2ZjXHVkNTU5XHVhY2UwXHVjNzU4IFx1YWQ2Y1x1Yzg3MFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3ODRcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDEwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSAxMF4zJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwIFx1YzgxY1x1ZDU1YyBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxMDcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVsaXZlcmluZyBOb29kbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5TZW91bCBTY2llbmNlIEhpZ2ggU2Nob29sKFNTSFMpIGRvcm1pdG9yeSBmb3JtcyBhIHRyZWUgd2l0aCAkTiQgcm9vbXMgY29ubmVjdGVkIHdpdGggJE4tMSQgY29ycmlkb3JzLiBFdmVyeSBjb3JyaWRvciBjYW4gYmUgcGFzc2VkIGluIGJvdGggZGlyZWN0aW9ucywgYW5kIGl0IGlzIHBvc3NpYmxlIHRvIHRyYXZlbCBiZXR3ZWVuIGFsbCByb29tcy4gVHJhdmVyc2luZyBhIGNvcnJpZG9yIHRha2VzICQxJCB1bml0IG9mIHRpbWUuPFwvcD5cclxuXHJcbjxwPk1pbmd5dSB3YW50cyB0byBwcmVwYXJlIG5vb2RsZXMgZm9yIGhpcyAkSyQgZnJpZW5kcy4gSGUgaXMgY3VycmVudGx5IGluIHJvb20gJDEkLCBhbmQgaGUgYW5kIGhpcyBmcmllbmRzIGFyZSBhbGwgaW4gZGlzdGluY3Qgcm9vbXMuPFwvcD5cclxuXHJcbjxwPk1pbmd5dSB3aWxsIHByb3ZpZGUgaG90IHdhdGVyIGZvciBhbGwgaGlzIGZyaWVuZHMuIEhlIGNhbiBvbmx5IG9idGFpbiBob3Qgd2F0ZXIgZnJvbSB0aGUgd2F0ZXIgcHVyaWZpZXIgaW4gaGlzIHJvb20gKG51bWJlcmVkICQxJCkuIEFkZGl0aW9uYWxseSwgaGUgaGFzIGEgYmlnIGJvdHRsZSwgc28gaGUgY2FuIGRlbGl2ZXIgd2F0ZXIgdG8gYWxsIGhpcyBmcmllbmRzIHdpdGhvdXQgbmVlZGluZyB0byBmaWxsIGhpcyBib3R0bGUgYWdhaW4uPFwvcD5cclxuXHJcbjxwPlByZXBhcmluZyBub29kbGVzIGlzIGRhbmdlcm91cy4gSWYgeW91IGdldCBjYXVnaHQgYnkgdGhlIGRvcm1pdG9yeSBzdXBlcnZpc29yLCB5b3Ugd2lsbCBnZXQgbWFueSBkZW1lcml0IHBvaW50cy4gVG8gcmVkdWNlIHRoZSByaXNrIG9mIGdldHRpbmcgY2F1Z2h0LCBoZSB3aWxsIHZpc2l0IHRoZSAkSyQgcm9vbXMgc28gdGhhdCB0aGUgdGltZSBvZiBoaXMgbGFzdCBkZWxpdmVyeSBpcyBhcyBlYXJseSBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+UHJlY2lzZWx5LCBoZSB2aXNpdHMgdGhlICRLJCByb29tcyB1c2luZyB0aGUgZm9sbG93aW5nIG1ldGhvZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5CZWZvcmUgZmlsbGluZyBoaXMgYm90dGxlIHdpdGggaG90IHdhdGVyLCBoZSBvYnRhaW5zIHRoZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgJEskIHJvb21zIHdoZXJlIGhpcyBmcmllbmRzIGFyZS48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgaGUgZmlsbHMgaGlzIGJvdHRsZSBmcm9tIHJvb20gJDEkIGluIHRpbWUgJDAkLCBoZSB2aXNpdHMgaGlzICRLJCBmcmllbmRzIGluIGFuIG9yZGVyIHN1Y2ggdGhhdCB0aGUgbGFzdCBkZWxpdmVyeSBpcyBhcyBlYXJseSBhcyBwb3NzaWJsZS48XC9saT5cclxuXHQ8bGk+V2Ugb25seSBjb25zaWRlciB0aGUgdGltZSBzcGVudCB3aGlsZSB3YWxraW5nIHRocm91Z2ggY29ycmlkb3JzLiBXZSBpZ25vcmUgdGhlIHRpbWUgZmlsbGluZyB0aGUgYm90dGxlIG9yIGRlbGl2ZXJpbmcgaG90IHdhdGVyIHRvIGhpcyBmcmllbmRzLiA8c3Ryb25nPldlIGFsc28gaWdub3JlIHRoZSB0aW1lIE1pbmd5dSByZXR1cm5zIHRvIGhpcyByb29tIGFmdGVyIGhpcyBsYXN0IGRlbGl2ZXJ5LjxcL3N0cm9uZz48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5CZWZvcmUgY2hlY2tpbmcgd2hhdCAkSyQgcm9vbXMgaGlzIGZyaWVuZHMgYXJlIGluLCBNaW5neXUgd2FudHMgdG8gcHJlZGljdCBob3cgbG9uZyBpdCB3aWxsIHRha2UgdG8gZGVsaXZlciB3YXRlciB0byBhbGwgaGlzIGZyaWVuZHMuIFBsZWFzZSBjYWxjdWxhdGUgdGhlIHN1bSBvZiB0aGUgZWFybGllc3QgcG9zc2libGUgdGltZSBvZiB0aGUgbGFzdCBkZWxpdmVyeSBmb3IgYWxsICRcXGJpbm9te04tMX17S30kIGRpZmZlcmVudCB3YXlzIGhpcyBmcmllbmRzIGNhbiBiZSBpbiB0aGVpciByb29tcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkTiQgYW5kICRLJCAmbWRhc2g7IHRoZSBudW1iZXIgb2Ygcm9vbXMgYW5kIHRoZSBudW1iZXIgb2YgZnJpZW5kcywgcmVzcGVjdGl2ZWx5LiBUaGV5IGFyZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+RnJvbSB0aGUgc2Vjb25kIGxpbmUgdG8gJE4kLXRoIGxpbmUsIHRoZSAkaSsxJC10aCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkVV9pJCBhbmQgJFZfaSQgJm1kYXNoOyB0aGUgcm9vbXMmcnNxdW87IGluZGV4IHdoaWNoIHRoZSAkaSQtdGggY29ycmlkb3IgY29ubmVjdHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUsIHByaW50IHRoZSBzdW0gb2YgdGhlIHRpbWUgb2YgdGhlIGxhc3QgZGVsaXZlcnkgZm9yIGFsbCAkXFxiaW5vbXtOLTF9e0t9JCBkaWZmZXJlbnQgd2F5cyBpbiB3aGljaCBoaXMgZnJpZW5kcyBjYW4gYmUgaW4gdGhlaXIgcm9vbXMsIG1vZHVsbyAkMTBeOSArIDckLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlIE5cXGxlIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBLXFxsZSBOLTEkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBVX2lcXGxlIE4kICQoMVxcbGUgaSZsdDtOKSQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIFZfaVxcbGUgTiQgJCgxXFxsZSBpJmx0O04pJDxcL2xpPlxyXG5cdDxsaT4kVV9pXFxuZSBWX2kkICQoMVxcbGUgaSZsdDtOKSQ8XC9saT5cclxuXHQ8bGk+VGhlIHN0cnVjdHVyZSBvZiBTU0hTIGRvcm1pdG9yeSBpbiB0aGUgaW5wdXQgZm9ybXMgYSB2YWxpZCB0cmVlLjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDEwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSAxMF4zJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+VGhlcmUgYXJlIG5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d

출처

School > 서울과학고등학교 > SciOI 2023 B-1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)