시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 19 10 71.429%

문제

3차 논리는 논리값이 "true", "false", "unknown"을 가지는 논리 체계이다. 이 체계에서는 "false"는 0의 값을 가지고, "unknown"은 1, "true"는 2의 값을 갖는다.

"-"을 단항 연산자, "*"와 "+"는 이항 연산자라고 하자. 이 연산자는 각각 NOT, AND, OR을 의미한다. 3차 논리에서 3개 연산자는 다음과 같이 정의되어 있다.

P, Q, R을 3차 논리값을 갖는 변수라고 하자. 이때, 식이 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍의 개수를 구하는 프로그램을 작성하시오. 식은 다음 중 하나의 형태를 갖는다. (X와 Y는 식을 의미한다)

  • 상수: 0, 1, 2
  • 변수: P, Q, R
  • NOT: -X
  • AND: (X*Y)
  • OR: (X+Y)

AND와 OR은 항상 괄호로 둘러쌓여 있다.

예를 들어, (P*Q)가 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍은 (2,2,0), (2,2,1), (2,2,2) 3가지이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 식을 나타낸다. 식은 0, 1, 2, P, Q, R, -, *, +, (, )로만 이루어져 있다.

식의 BNF형 문법은 다음과 같다.

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

        

입력은 80글자를 넘지 않는다. 마지막 줄에는 '.'이 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 식의 값을 2로 만드는 (P,Q,R) 쌍의 개수를 출력한다.

예제 입력 1

(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.

예제 출력 1

3
11
0
27
0
7
W3sicHJvYmxlbV9pZCI6IjQ5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1MTRcdWM5YzBcdWQxMzggXHVkNjhjXHViODVjIFx1YWMxY1x1Yjg2MCIsImRlc2NyaXB0aW9uIjoiPHA+M1x1Y2MyOCBcdWIxN2NcdWI5YWNcdWIyOTQgXHViMTdjXHViOWFjXHVhYzEyXHVjNzc0ICZxdW90O3RydWUmcXVvdDssICZxdW90O2ZhbHNlJnF1b3Q7LCAmcXVvdDt1bmtub3duJnF1b3Q7XHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWIxN2NcdWI5YWMgXHVjY2I0XHVhY2M0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjY2I0XHVhY2M0XHVjNWQwXHVjMTFjXHViMjk0ICZxdW90O2ZhbHNlJnF1b3Q7XHViMjk0IDBcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCwgJnF1b3Q7dW5rbm93biZxdW90O1x1Yzc0MCAxLCAmcXVvdDt0cnVlJnF1b3Q7XHViMjk0IDJcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD4mcXVvdDstJnF1b3Q7XHVjNzQ0IFx1YjJlOFx1ZDU2ZCBcdWM1ZjBcdWMwYjBcdWM3OTAsICZxdW90OyomcXVvdDtcdWM2NDAgJnF1b3Q7KyZxdW90O1x1YjI5NCBcdWM3NzRcdWQ1NmQgXHVjNWYwXHVjMGIwXHVjNzkwXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YzVmMFx1YzBiMFx1Yzc5MFx1YjI5NCBcdWFjMDFcdWFjMDEgTk9ULCBBTkQsIE9SXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gM1x1Y2MyOCBcdWIxN2NcdWI5YWNcdWM1ZDBcdWMxMWMgM1x1YWMxYyBcdWM1ZjBcdWMwYjBcdWM3OTBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg3cHg7IHdpZHRoOjQ0NnB4XCIgXC8+PFwvcD5cclxuXHJcblxyXG5cclxuPHA+UCwgUSwgUlx1Yzc0NCAzXHVjYzI4IFx1YjE3Y1x1YjlhY1x1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViY2MwXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCAyXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoUCxRLFIpXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMmRkXHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIChYXHVjNjQwIFlcdWIyOTQgXHVjMmRkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuXHJcblxyXG48dWw+XHJcbjxsaT5cdWMwYzFcdWMyMTg6IDAsIDEsIDI8XC9saT5cclxuXHJcbjxsaT5cdWJjYzBcdWMyMTg6IFAsIFEsIFI8XC9saT5cclxuXHJcbjxsaT5OT1Q6IC1YPFwvbGk+XHJcblxyXG48bGk+QU5EOiAoWCpZKTxcL2xpPlxyXG5cclxuPGxpPk9SOiAoWCtZKTxcL2xpPjxcL3VsPlxyXG5cclxuXHJcbjxwPkFORFx1YzY0MCBPUlx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVhZDA0XHVkNjM4XHViODVjIFx1YjQ1OFx1YjdlY1x1YzMxM1x1YzVlYyBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKFAqUSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCAyXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoUCxRLFIpXHVjMzBkXHVjNzQwICgyLDIsMCksICgyLDIsMSksICgyLDIsMikgM1x1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzJkZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzJkZFx1Yzc0MCAwLCAxLCAyLCBQLCBRLCBSLCAtLCAqLCArLCAoLCApXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjMmRkXHVjNzU4IEJORlx1ZDYxNSBcdWJiMzhcdWJjOTVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cHJlPlxyXG4mbHQ7Zm9ybXVsYSZndDsgOjo9IDAgfCAxIHwgMiB8IFAgfCBRIHwgUiB8XHJcbiAgICAgICAgICAgICAgLSZsdDtmb3JtdWxhJmd0OyB8ICgmbHQ7Zm9ybXVsYSZndDsqJmx0O2Zvcm11bGEmZ3Q7KSB8ICgmbHQ7Zm9ybXVsYSZndDsrJmx0O2Zvcm11bGEmZ3Q7KTxcL3ByZT5cclxuXHJcbjxwPiAmbmJzcDsgJm5ic3A7ICZuYnNwOyAmbmJzcDsmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzQwIDgwXHVhZTAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTsuJiMzOTtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyZGRcdWM3NTggXHVhYzEyXHVjNzQ0IDJcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IChQLFEsUikgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDk3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvdyBjYW4gSSBzYXRpc2Z5IHRoZWU/IExldCBtZSBjb3VudCB0aGUgd2F5cy4uLiIsImRlc2NyaXB0aW9uIjoiPHA+VGhyZWUtdmFsdWVkIGxvZ2ljIGlzIGEgbG9naWMgc3lzdGVtIHRoYXQgaGFzLCBpbiBhZGRpdGlvbiB0byAmcXVvdDt0cnVlJnF1b3Q7IGFuZCAmcXVvdDtmYWxzZSZxdW90OywgJnF1b3Q7dW5rbm93biZxdW90OyBhcyBhIHZhbGlkIHZhbHVlLiBJbiB0aGUgZm9sbG93aW5nLCBsb2dpY2FsIHZhbHVlcyAmcXVvdDtmYWxzZSZxdW90OywgJnF1b3Q7dW5rbm93biZxdW90OyBhbmQgJnF1b3Q7dHJ1ZSZxdW90OyBhcmUgcmVwcmVzZW50ZWQgYnkgMCwgMSBhbmQgMiByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPkxldCAmcXVvdDstJnF1b3Q7IGJlIGEgdW5hcnkgb3BlcmF0b3IgKGkuZS4gYSBzeW1ib2wgcmVwcmVzZW50aW5nIG9uZSBhcmd1bWVudCBmdW5jdGlvbikgYW5kIGxldCBib3RoICZxdW90OyomcXVvdDsgYW5kICZxdW90OysmcXVvdDsgYmUgYmluYXJ5IG9wZXJhdG9ycyAoaS5lLiBzeW1ib2xzIHJlcHJlc2VudGluZyB0d28gYXJndW1lbnQgZnVuY3Rpb25zKS4gVGhlc2Ugb3BlcmF0b3JzIHJlcHJlc2VudCBuZWdhdGlvbiAoTk9UKSwgY29uanVuY3Rpb24gKEFORCkgYW5kIGRpc2p1bmN0aW9uIChPUikgcmVzcGVjdGl2ZWx5LiBUaGVzZSBvcGVyYXRvcnMgaW4gdGhyZWUtdmFsdWVkIGxvZ2ljIGNhbiBiZSBkZWZpbmVkIGluIFRhYmxlIEMtMS48XC9wPlxyXG5cclxuPHA+VGFibGUgQy0xOiBUcnV0aCB0YWJsZXMgb2YgdGhyZWUtdmFsdWVkIGxvZ2ljIG9wZXJhdG9ycyZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3R2LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4N3B4OyB3aWR0aDo0NDZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5MZXQgUCwgUSBhbmQgUiBiZSB2YXJpYWJsZXMgcmFuZ2luZyBvdmVyIHRocmVlLXZhbHVlZCBsb2dpYyB2YWx1ZXMuIEZvciBhIGdpdmVuIGZvcm11bGEsIHlvdSBhcmUgYXNrZWQgdG8gYW5zd2VyIHRoZSBudW1iZXIgb2YgdHJpcGxlcyAoUCxRLFIpIHRoYXQgc2F0aXNmeSB0aGUgZm9ybXVsYSwgdGhhdCBpcywgdGhvc2Ugd2hpY2ggbWFrZSB0aGUgdmFsdWUgb2YgdGhlIGdpdmVuIGZvcm11bGEgMi4gQSBmb3JtdWxhIGlzIG9uZSBvZiB0aGUgZm9sbG93aW5nIGZvcm0gKFggYW5kIFkgcmVwcmVzZW50IGZvcm11bGFzKS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Db25zdGFudHM6IDAsIDEgb3IgMjxcL2xpPlxyXG5cdDxsaT5WYXJpYWJsZXM6IFAsIFEgb3IgUjxcL2xpPlxyXG5cdDxsaT5OZWdhdGlvbnM6IC1YPFwvbGk+XHJcblx0PGxpPkNvbmp1bmN0aW9uczogKFgqWSk8XC9saT5cclxuXHQ8bGk+RGlzanVuY3Rpb25zOiAoWCtZKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGUgdGhhdCBjb25qdW5jdGlvbnMgYW5kIGRpc2p1bmN0aW9ucyBvZiB0d28gZm9ybXVsYXMgYXJlIGFsd2F5cyBwYXJlbnRoZXNpemVkLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgd2hlbiBmb3JtdWxhIChQKlEpIGlzIGdpdmVuIGFzIGFuIGlucHV0LCB0aGUgdmFsdWUgb2YgdGhpcyBmb3JtdWxhIGlzIDIgd2hlbiBhbmQgb25seSB3aGVuIChQLFEsUikgaXMgKDIsMiwwKSwgKDIsMiwxKSBvciAoMiwyLDIpLiBUaGVyZWZvcmUsIHlvdSBzaG91bGQgb3V0cHV0IDMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgbGluZXMuIEVhY2ggbGluZSBjb250YWlucyBhIGZvcm11bGEuIEEgZm9ybXVsYSBpcyBhIHN0cmluZyB3aGljaCBjb25zaXN0cyBvZiAwLCAxLCAyLCBQLCBRLCBSLCAtLCAqLCArLCAoLCApLiBPdGhlciBjaGFyYWN0ZXJzIHN1Y2ggYXMgc3BhY2VzIGFyZSBub3QgY29udGFpbmVkLiBUaGUgZ3JhbW1hciBvZiBmb3JtdWxhcyBpcyBnaXZlbiBieSB0aGUgZm9sbG93aW5nIEJORi48XC9wPlxyXG5cclxuPHByZT5cclxuJmx0O2Zvcm11bGEmZ3Q7IDo6PSAwIHwgMSB8IDIgfCBQIHwgUSB8IFIgfFxyXG4gICAgICAgICAgICAgIC0mbHQ7Zm9ybXVsYSZndDsgfCAoJmx0O2Zvcm11bGEmZ3Q7KiZsdDtmb3JtdWxhJmd0OykgfCAoJmx0O2Zvcm11bGEmZ3Q7KyZsdDtmb3JtdWxhJmd0Oyk8XC9wcmU+XHJcblxyXG48cD5BbGwgdGhlIGZvcm11bGFzIG9iZXkgdGhpcyBzeW50YXggYW5kIHRodXMgeW91IGRvIG5vdCBoYXZlIHRvIGNhcmUgYWJvdXQgZ3JhbW1hdGljYWwgZXJyb3JzLiBJbnB1dCBsaW5lcyBuZXZlciBleGNlZWQgODAgY2hhcmFjdGVycy48XC9wPlxyXG5cclxuPHA+RmluYWxseSwgYSBsaW5lIHdoaWNoIGNvbnRhaW5zIG9ubHkgYSAmcXVvdDsuJnF1b3Q7IChwZXJpb2QpIGNvbWVzLCBpbmRpY2F0aW5nIHRoZSBlbmQgb2YgdGhlIGlucHV0PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91IHNob3VsZCBhbnN3ZXIgdGhlIG51bWJlciAoaW4gZGVjaW1hbCkgb2YgdHJpcGxlcyAoUCxRLFIpIHRoYXQgbWFrZSB0aGUgdmFsdWUgb2YgdGhlIGdpdmVuIGZvcm11bGEgMi4gT25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIHNob3VsZCBiZSBvdXRwdXQgZm9yIGVhY2ggb2YgdGhlIGZvcm11bGFzLCBhbmQgbm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYmUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==