이 문제 설명에 등장하는 이야기, 이름, 인물, 사건은 모두 허구이다. 실제 인물과의 동일시를 의도하지 않으며, 그렇게 추론해서도 안 된다.

1935년, 두 명의 노벨상 수상자가 만나 놀라운 결과를 만들어 내고 있다. 유명한 물리학자 슈뢰딩거(Schrödinger)는 유명한 생리학자 파블로프(Pavlov)를 초대해 상자 속 고양이 실험을 보여 주었다. 파블로프는 자신의 연구를 계속하기 위해 개도 함께 데려왔고, 이 조합은 말 그대로 흥미로웠다.

슈뢰딩거는 \mathbf{N}개의 상자를 일렬로 놓아 두었다. 어떤 상자에는 고양이가 확실히 있고, 어떤 상자에는 확실히 없으며, 어떤 상자에는 있을 수도 없을 수도 있다. 각 상자는 고양이 한 마리만 들어갈 수 있을 만큼만 크다. 또한 각 상자에는 특수한 양자 터널이 달려 있어, 목적지 상자가 비어 있다면 상자 안의 고양이가 특정 다른 상자로 이동할 수 있다. 터널은 한 방향으로만 작동한다.

고양이들은 보통 온순하고 조용해서, 깜짝 놀라지 않으면 터널을 사용하지 않는다. 그런데 초대받지 않은 세 번째 손님이 벨을 누르자, 파블로프의 개는 즉시 흥분해 달리고 짖기 시작한다. 개는 1번 상자에서 출발해 \mathbf{N}번 상자 쪽으로 달려간다. 개가 달리는 동안, 각 상자를 하나씩 지나가며 바로 옆을 스친다. 고양이가 들어 있는 상자 옆을 지나갈 때마다, 그 상자 안의 고양이는 깜짝 놀란다. 깜짝 놀란 고양이는 가능한 터널을 확인하고, 목적지 상자가 비어 있다면 그 터널을 이용해 도망친다. 목적지 상자가 차 있다면, 고양이는 현재 상자에 그대로 남는다. 고양이가 개가 나중에 지나갈 상자로 이동했다면, 같은 고양이가 여러 번 놀랄 수도 있으며, 놀랄 때마다 같은 방식으로 행동한다 (매번 그 시점에 사용할 수 있는 터널 하나만을 고려한다).

Illustration of Sample Case #1 with a dog shown walking from left to right.

파블로프의 개가 마침내 마지막 상자 옆에서 멈춘 뒤, 파블로프는 슈뢰딩거에게 마지막 상자에 고양이가 있는지 묻는다. 슈뢰딩거는 자신의 명성에 걸맞게, 모른다고 답한다. 파블로프는 답이 미지의 상자들에 실제로 고양이가 있었는지에 따라 달라질 수 있음을 알아차렸다. 또한 미지의 상자가 k개라면, 각 상자의 상태 조합마다 하나씩 총 2^k개의 초기 구성(initial configuration)이 가능함도 알아차렸다. 파블로프는 슈뢰딩거에게, 이 2^k개의 초기 구성 중 마지막 상자에 고양이가 남게 되는 경우가 몇 개인지 계산해 보자고 제안한다. 당신의 과제는 그 계산을 재현하는 것이다. 결과는 매우 클 수 있으므로, 소수 10^9+7(1000000007)로 나눈 나머지만 출력하면 된다.

이 문제 설명을 만드는 동안 고양이도, 개도, 노벨상 수상자도 피해를 입지 않았다.

#10446 upload 1 done 1 how_to_reg 1

Schrödinger and Pavlov timer 10s memory 1024MB

#10446

Schrödinger and Pavlov 10s 1024MB