Задача . F. Мультимножество строк

Вам даны три целых числа \(n\), \(k\) и \(f\).

Рассмотрим все бинарные строки (то есть все строки, состоящие из символов \(0\) и/или \(1\)) длины от \(1\) до \(n\). Для каждой такой строки \(s\) вы должны выбрать целое число \(c_s\) от \(0\) до \(k\).

Мультимножество из бинарных строк длины ровно \(n\) считается красивым, если для каждой бинарной строки \(s\) длины от \(1\) до \(n\) выполняется следующее: количество строк в мультимножестве, для которых \(s\) является префиксом, не превосходит \(c_s\).

Например, пусть \(n = 2\), \(c_{0} = 3\), \(c_{00} = 1\), \(c_{01} = 2\), \(c_{1} = 1\), \(c_{10} = 2\) и \(c_{11} = 3\). Мультимножество строк \(\{11, 01, 00, 01\}\) является красивым, так как:

• для строки \(0\) существует \(3\) строки из мультимножества, для которых \(0\) — префикс, и \(3 \le c_0\);
• для строки \(00\) существует одна строка из мультимножества, для которой \(00\) — префикс, и \(1 \le c_{00}\);
• для строки \(01\) существует \(2\) строки из мультимножества, для которых \(01\) — префикс, и \(2 \le c_{01}\);
• для строки \(1\) существует одна строка из мультимножества, для которой \(1\) — префикс, и \(1 \le c_1\);
• для строки \(10\) существует \(0\) строк из мультимножества, для которых \(10\) — префикс, и \(0 \le c_{10}\);
• для строки \(11\) существует одна строка из мультимножества, для которой \(11\) — префикс, и \(1 \le c_{11}\).

А теперь — сама задача. Вы должны посчитать количество способов выбрать числа \(c_s\) для всех бинарных строк \(s\) длины от \(1\) до \(n\) таким образом, чтобы максимальный возможный размер красивого мультимножества был равен ровно \(f\).