За столом в ряд сидят n человек. Про каждого человека известно, что он либо всегда говорит правду, либо всегда лжет.

Маленький Сережа спросил их: сколько среди вас человек, которые всегда говорят правду? Каждый из сидящих за столом знает всю информацию (кто правдивый человек, а кто врун) про всех людей, сидящих за столом. Правдивые люди скажут правильный ответ, вруны скажут любое целое число от 1 до n, которое не является правильным ответом. Каждый врун выбирается свой ответ независимо от остальных врунов, поэтому ответы двух разных врунов могут отличаться.

Сережа не знает никакой информации про людей, кроме их ответов на заданный вопрос. Он записал на листок бумаги n целых чисел a₁, a₂, ..., a_n, где a_i — ответ i-го в ряду человека. По этой последовательности Сережа определил, что ровно k человек из сидящих за столом точно врут.

Сереже интересно, сколько существует вариантов ответов людей (последовательностей ответов a длины n), при которых можно будет сказать, что ровно k человек, из сидящих за столом, точно врут. Так как описанных вариантов ответов может быть достаточно много, посчитайте остаток от деления количества вариантов на 777777777.