문제
$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다.
돌들을 왼쪽부터 1번 돌, 2번 돌,..., $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.
당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.
돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.
돌을 가져가는 방법은 순서에 따라 총 $N!$가지 서로 다른 방법이 존재한다. 가능한 $N!$가지 방법에서 얻을 수 있는 점수의 총합을 구하여라.
출력
첫째 줄에 $N!$가지 방법에서 얻을 수 있는 점수의 총합을 998ドル\ 244\ 353$으로 나눈 나머지를 출력한다.
노트
왼쪽에서 두 번째 돌을 가져가면서 점수를 얻는 방법과 세 번째 돌을 가져가면서 점수를 얻는 방법이 각각 8가지씩 있다. 따라서 총 점수는 8ドル \times 4 + 8 \times 5 = 72$ 점이다.
W3sicHJvYmxlbV9pZCI6IjIyODc5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCAyIiwiZGVzY3JpcHRpb24iOiI8cD4kTiQgXHVhYzFjXHVjNzU4IFx1YjNjY1x1Yzc3NCBcdWM3N2NcdWI4MmNcdWI4NWMgXHViMDk4XHVjNWY0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YjNjY1x1Yzc0MCBcdWQ3NzBcdWMwYzkgXHViNjEwXHViMjk0IFx1YWM4MFx1Yzc0MFx1YzBjOVx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVhYzE2XHViMjk0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIzY2NcdWI0ZTRcdWM3NDQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIDFcdWJjODggXHViM2NjLCAyXHViYzg4IFx1YjNjYywuLi4sICROJFx1YmM4OCBcdWIzY2NcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiAkaSRcdWJjODhcdWM5ZjggXHViM2NjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1YjI5NCAkQV9pJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YjA5OFx1YzVmNFx1YjQxYyBcdWIzY2NcdWI0ZTQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2MgXHVhYzAwXHVjODM4XHVhYzAwXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJhYThcdWI0ZTAgXHViM2NjXHVjNzc0IFx1YzVjNlx1YzViNFx1YzljOCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjZDFkICROJFx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzY2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzA4IFx1YjU0YywgXHViOWNjXHVjNTdkIFx1YWRmOCBcdWIzY2NcdWM3NzQgXHVkNjA0XHVjN2FjIFx1YjA5OFx1YzVmNFx1YjQxYyBcdWIzY2MgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM3NzRcdWIwOTggXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWJhNzAsIFx1YWMwMFx1YzgzOFx1YWMwNCBcdWIzY2NcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWIzY2MgXHViYWE4XHViNDUwIFx1YWMwMFx1YzgzOFx1YWMwNCBcdWIzY2NcdWFjZmMgXHViMmU0XHViOTc4IFx1YzBjOVx1Yzc3OCBcdWFjYmRcdWM2YjAgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWMwMFx1YzgzOFx1YWMwNCBcdWIzY2NcdWM3NTggXHViYjM0XHVhYzhjXHViOWNjXHVkMDdjXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjY1x1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzIxY1x1YzExY1x1YzVkMCBcdWI1MzBcdWI3N2MgXHVjZDFkICROISRcdWFjMDBcdWM5YzAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgJE4hJFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM1ZDBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgTiBcXGxlIDIgXFx0aW1lcyAxMF41JCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCA8Y29kZT5CPFwvY29kZT4gXHViNjEwXHViMjk0IDxjb2RlPlc8XC9jb2RlPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JFMkXHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAgJFNfaSRcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjICRpJFx1YmM4OFx1YzlmOCBcdWIzY2NcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gPGNvZGU+QjxcL2NvZGU+XHViMjk0IFx1YjNjY1x1Yzc3NCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3ODRcdWM3NDQsIDxjb2RlPlc8XC9jb2RlPlx1YjI5NCBcdWIzY2NcdWM3NzQgXHVkNzcwXHVjMGM5XHVjNzg0XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMSBcXGxlIEFfaSBcXGxlIDEwXjkkKTxcL3A+XHJcblxyXG48cD4kQV9pJCBcdWIyOTQgJGkkXHViYzg4IFx1YjNjY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4hJFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM1ZDBcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCAkOTk4XFwgMjQ0XFwgMzUzJFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YmE3NFx1YzExYyBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHViMjk0IFx1YmMyOVx1YmM5NVx1YWNmYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YjNjY1x1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzRcdWMxMWMgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVhYzAxXHVhYzAxIDhcdWFjMDBcdWM5YzBcdWM1MjkgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjZDFkIFx1YzgxMFx1YzIxOFx1YjI5NCAkOCBcXHRpbWVzIDQgKyA4IFxcdGltZXMgNSA9IDcyJCBcdWM4MTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMjg3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0b25lcyAyIiwiZGVzY3JpcHRpb24iOiI8cD4kTiQmbmJzcDtzdG9uZXMgbGFiZWxlZCBmcm9tJm5ic3A7JDEkJm5ic3A7dG8mbmJzcDskTiQmbmJzcDthcmUgYXJyYW5nZWQgaW4gYSByb3cgaW4gaW5jcmVhc2luZyBvcmRlci4gRWFjaCBzdG9uZSBpcyBjb2xvcmVkIGVpdGhlciB3aGl0ZSBvciBibGFjay4gVGhlIHdlaWdodCBvZiB0aGUmbmJzcDskaSQtdGggc3RvbmUgaXMmbmJzcDskQV9pJC48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgcmVtb3ZlIHRoZSBzdG9uZXMgb25lIGF0IGEgdGltZSB1bnRpbCBhbGwgdGhlIHN0b25lcyBhcmUgcmVtb3ZlZC48XC9wPlxyXG5cclxuPHA+V2hlbiByZW1vdmluZyBhIHN0b25lLCBpZiB0aGUgc3RvbmUgaXMgbm90IHRoZSBsZWZ0bW9zdCBvciByaWdodG1vc3Qgb2YgYWxsIHJlbWFpbmluZyBzdG9uZXMsIGFuZCBuZWl0aGVyIHN0b25lIGFkamFjZW50IHRvIHRoZSBzdG9uZSBiZWluZyByZW1vdmVkIG1hdGNoZXMgaXQgaW4gY29sb3IsIHlvdXIgc2NvcmUgaW5jcmVhc2VzIGJ5IHRoZSB3ZWlnaHQgb2YgdGhlIHN0b25lIGJlaW5nIHJlbW92ZWQuIFR3byBzdG9uZXMgYXJlIGFkamFjZW50IGlmIHRoZXJlIGFyZSBubyBzdG9uZXMgaW4gYmV0d2VlbiB0aG9zZSB0d28uPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSZuYnNwOyROISQmbmJzcDtwb3NzaWJsZSB3YXlzIHRvIHJlbW92ZSBhbGwgdGhlIHN0b25lcy4gQ29tcHV0ZSB0aGUgc3VtIG9mIHNjb3JlcyBmcm9tIGVhY2ggcG9zc2libGUgd2F5LCBtb2R1bG8mbmJzcDskOTk4XFwsMjQ0XFwsMzUzJC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXImbmJzcDskTiQmbmJzcDsoJDEgXFxsZSBOIFxcbGUgMzAwXFwsIDAwMCQpLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzdHJpbmcmbmJzcDskUyQmbmJzcDtvZiBsZW5ndGgmbmJzcDskTiQmbmJzcDt3aGVyZSBlYWNoIGNoYXJhY3RlciBpcyBlaXRoZXImbmJzcDs8Y29kZT5CPFwvY29kZT4mbmJzcDtvciZuYnNwOzxjb2RlPlc8XC9jb2RlPi4gVGhlJm5ic3A7JGkkdGggY2hhcmFjdGVyIG9mJm5ic3A7JFMkLCZuYnNwOyRTX2kkLCBpcyZuYnNwOzxjb2RlPkI8XC9jb2RlPiZuYnNwO2lmIHRoZSZuYnNwOyRpJC10aCBzdG9uZSBpcyBibGFjaywgb3RoZXJ3aXNlLCZuYnNwOyRTX2kkJm5ic3A7aXMmbmJzcDs8Y29kZT5XPFwvY29kZT4mbmJzcDthbmQgdGhlJm5ic3A7JGkkLXRoIHN0b25lIGlzIHdoaXRlLjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyZuYnNwOyROJCZuYnNwO2ludGVnZXJzJm5ic3A7JEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kJm5ic3A7KCQxIFxcbGUgQV9pIFxcbGUgMTBeOSQpLiZuYnNwOyRBX2kkJm5ic3A7cmVwcmVzZW50cyB0aGUgd2VpZ2h0IG9mIHN0b25lJm5ic3A7JGkkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc3VtIG9mIHRoZSBzY29yZXMgb3ZlciBhbGwgcG9zc2libGUgd2F5cyB0byB0YWtlIHRoZSBzdG9uZXMsIG1vZHVsbyZuYnNwOyQ5OThcXCwyNDRcXCwzNTMkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=