Вам даны три целых числа $$$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$$$.