시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 7 5 62.500%

문제

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+UCwgUSwgUlx1Yzc0NCAzXHVjYzI4IFx1YjE3Y1x1YjlhY1x1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViY2MwXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHVjMmRkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJkZFx1Yzc1OCBcdWFjMTJcdWM3NDQgMlx1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgKFAsUSxSKVx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzJkZFx1Yzc0MCBcdWIyZTRcdWM3NGMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI5N2MgXHVhYzE2XHViMjk0XHViMmU0LiAoWFx1YzY0MCBZXHViMjk0IFx1YzJkZFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcblxyXG5cclxuPHVsPlxyXG48bGk+XHVjMGMxXHVjMjE4OiAwLCAxLCAyPFwvbGk+XHJcblxyXG48bGk+XHViY2MwXHVjMjE4OiBQLCBRLCBSPFwvbGk+XHJcblxyXG48bGk+Tk9UOiAtWDxcL2xpPlxyXG5cclxuPGxpPkFORDogKFgqWSk8XC9saT5cclxuXHJcbjxsaT5PUjogKFgrWSk8XC9saT48XC91bD5cclxuXHJcblxyXG48cD5BTkRcdWM2NDAgT1JcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWQwNFx1ZDYzOFx1Yjg1YyBcdWI0NThcdWI3ZWNcdWMzMTNcdWM1ZWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIChQKlEpXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJkZFx1Yzc1OCBcdWFjMTJcdWM3NDQgMlx1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgKFAsUSxSKVx1YzMwZFx1Yzc0MCAoMiwyLDApLCAoMiwyLDEpLCAoMiwyLDIpIDNcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWMyZGRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMyZGRcdWM3NDAgMCwgMSwgMiwgUCwgUSwgUiwgLSwgKiwgKywgKCwgKVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzJkZFx1Yzc1OCBCTkZcdWQ2MTUgXHViYjM4XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHByZT5cclxuJmx0O2Zvcm11bGEmZ3Q7IDo6PSAwIHwgMSB8IDIgfCBQIHwgUSB8IFIgfFxyXG4gICAgICAgICAgICAgIC0mbHQ7Zm9ybXVsYSZndDsgfCAoJmx0O2Zvcm11bGEmZ3Q7KiZsdDtmb3JtdWxhJmd0OykgfCAoJmx0O2Zvcm11bGEmZ3Q7KyZsdDtmb3JtdWxhJmd0Oyk8XC9wcmU+XHJcblxyXG48cD4gJm5ic3A7ICZuYnNwOyAmbmJzcDsgJm5ic3A7Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCA4MFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICYjMzk7LiYjMzk7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCAyXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoUCxRLFIpIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb3cgY2FuIEkgc2F0aXNmeSB0aGVlPyBMZXQgbWUgY291bnQgdGhlIHdheXMuLi4iLCJkZXNjcmlwdGlvbiI6IjxwPlRocmVlLXZhbHVlZCBsb2dpYyBpcyBhIGxvZ2ljIHN5c3RlbSB0aGF0IGhhcywgaW4gYWRkaXRpb24gdG8gJnF1b3Q7dHJ1ZSZxdW90OyBhbmQgJnF1b3Q7ZmFsc2UmcXVvdDssICZxdW90O3Vua25vd24mcXVvdDsgYXMgYSB2YWxpZCB2YWx1ZS4gSW4gdGhlIGZvbGxvd2luZywgbG9naWNhbCB2YWx1ZXMgJnF1b3Q7ZmFsc2UmcXVvdDssICZxdW90O3Vua25vd24mcXVvdDsgYW5kICZxdW90O3RydWUmcXVvdDsgYXJlIHJlcHJlc2VudGVkIGJ5IDAsIDEgYW5kIDIgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5MZXQgJnF1b3Q7LSZxdW90OyBiZSBhIHVuYXJ5IG9wZXJhdG9yIChpLmUuIGEgc3ltYm9sIHJlcHJlc2VudGluZyBvbmUgYXJndW1lbnQgZnVuY3Rpb24pIGFuZCBsZXQgYm90aCAmcXVvdDsqJnF1b3Q7IGFuZCAmcXVvdDsrJnF1b3Q7IGJlIGJpbmFyeSBvcGVyYXRvcnMgKGkuZS4gc3ltYm9scyByZXByZXNlbnRpbmcgdHdvIGFyZ3VtZW50IGZ1bmN0aW9ucykuIFRoZXNlIG9wZXJhdG9ycyByZXByZXNlbnQgbmVnYXRpb24gKE5PVCksIGNvbmp1bmN0aW9uIChBTkQpIGFuZCBkaXNqdW5jdGlvbiAoT1IpIHJlc3BlY3RpdmVseS4gVGhlc2Ugb3BlcmF0b3JzIGluIHRocmVlLXZhbHVlZCBsb2dpYyBjYW4gYmUgZGVmaW5lZCBpbiBUYWJsZSBDLTEuPFwvcD5cclxuXHJcbjxwPlRhYmxlIEMtMTogVHJ1dGggdGFibGVzIG9mIHRocmVlLXZhbHVlZCBsb2dpYyBvcGVyYXRvcnMmbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90di5wbmdcIiBzdHlsZT1cImhlaWdodDoxODdweDsgd2lkdGg6NDQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TGV0IFAsIFEgYW5kIFIgYmUgdmFyaWFibGVzIHJhbmdpbmcgb3ZlciB0aHJlZS12YWx1ZWQgbG9naWMgdmFsdWVzLiBGb3IgYSBnaXZlbiBmb3JtdWxhLCB5b3UgYXJlIGFza2VkIHRvIGFuc3dlciB0aGUgbnVtYmVyIG9mIHRyaXBsZXMgKFAsUSxSKSB0aGF0IHNhdGlzZnkgdGhlIGZvcm11bGEsIHRoYXQgaXMsIHRob3NlIHdoaWNoIG1ha2UgdGhlIHZhbHVlIG9mIHRoZSBnaXZlbiBmb3JtdWxhIDIuIEEgZm9ybXVsYSBpcyBvbmUgb2YgdGhlIGZvbGxvd2luZyBmb3JtIChYIGFuZCBZIHJlcHJlc2VudCBmb3JtdWxhcykuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q29uc3RhbnRzOiAwLCAxIG9yIDI8XC9saT5cclxuXHQ8bGk+VmFyaWFibGVzOiBQLCBRIG9yIFI8XC9saT5cclxuXHQ8bGk+TmVnYXRpb25zOiAtWDxcL2xpPlxyXG5cdDxsaT5Db25qdW5jdGlvbnM6IChYKlkpPFwvbGk+XHJcblx0PGxpPkRpc2p1bmN0aW9uczogKFgrWSk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ob3RlIHRoYXQgY29uanVuY3Rpb25zIGFuZCBkaXNqdW5jdGlvbnMgb2YgdHdvIGZvcm11bGFzIGFyZSBhbHdheXMgcGFyZW50aGVzaXplZC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHdoZW4gZm9ybXVsYSAoUCpRKSBpcyBnaXZlbiBhcyBhbiBpbnB1dCwgdGhlIHZhbHVlIG9mIHRoaXMgZm9ybXVsYSBpcyAyIHdoZW4gYW5kIG9ubHkgd2hlbiAoUCxRLFIpIGlzICgyLDIsMCksICgyLDIsMSkgb3IgKDIsMiwyKS4gVGhlcmVmb3JlLCB5b3Ugc2hvdWxkIG91dHB1dCAzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG9uZSBvciBtb3JlIGxpbmVzLiBFYWNoIGxpbmUgY29udGFpbnMgYSBmb3JtdWxhLiBBIGZvcm11bGEgaXMgYSBzdHJpbmcgd2hpY2ggY29uc2lzdHMgb2YgMCwgMSwgMiwgUCwgUSwgUiwgLSwgKiwgKywgKCwgKS4gT3RoZXIgY2hhcmFjdGVycyBzdWNoIGFzIHNwYWNlcyBhcmUgbm90IGNvbnRhaW5lZC4gVGhlIGdyYW1tYXIgb2YgZm9ybXVsYXMgaXMgZ2l2ZW4gYnkgdGhlIGZvbGxvd2luZyBCTkYuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiZsdDtmb3JtdWxhJmd0OyA6Oj0gMCB8IDEgfCAyIHwgUCB8IFEgfCBSIHxcclxuICAgICAgICAgICAgICAtJmx0O2Zvcm11bGEmZ3Q7IHwgKCZsdDtmb3JtdWxhJmd0OyombHQ7Zm9ybXVsYSZndDspIHwgKCZsdDtmb3JtdWxhJmd0OysmbHQ7Zm9ybXVsYSZndDspPFwvcHJlPlxyXG5cclxuPHA+QWxsIHRoZSBmb3JtdWxhcyBvYmV5IHRoaXMgc3ludGF4IGFuZCB0aHVzIHlvdSBkbyBub3QgaGF2ZSB0byBjYXJlIGFib3V0IGdyYW1tYXRpY2FsIGVycm9ycy4gSW5wdXQgbGluZXMgbmV2ZXIgZXhjZWVkIDgwIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPkZpbmFsbHksIGEgbGluZSB3aGljaCBjb250YWlucyBvbmx5IGEgJnF1b3Q7LiZxdW90OyAocGVyaW9kKSBjb21lcywgaW5kaWNhdGluZyB0aGUgZW5kIG9mIHRoZSBpbnB1dDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBzaG91bGQgYW5zd2VyIHRoZSBudW1iZXIgKGluIGRlY2ltYWwpIG9mIHRyaXBsZXMgKFAsUSxSKSB0aGF0IG1ha2UgdGhlIHZhbHVlIG9mIHRoZSBnaXZlbiBmb3JtdWxhIDIuIE9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBzaG91bGQgYmUgb3V0cHV0IGZvciBlYWNoIG9mIHRoZSBmb3JtdWxhcywgYW5kIG5vIG90aGVyIGNoYXJhY3RlcnMgc2hvdWxkIGJlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=