Background

As everyone knows, $lty$ really likes the two digits $96$ (if your mind went the wrong way, go face the wall right now), even more than repeating a grade (a repeating student)!

Problem Description

Because of “loving what someone loves”, $lty$ also likes numbers that “contain $96$”. Here, “contain” does not mean the usual kind of contain, but must satisfy all of the following properties (all three must be met):

• The number is an $N$-digit number and has no leading zeros.
• In this number, the digits $9$ and $6$ appear at least $M$ times in total (example: $986996$ has $5$ occurrences in total: $9$ appears $3$ times and $6$ appears $2$ times, for a total of $5$).
• There exist three consecutive digits $A$, $B$, $C$ that satisfy at least one of the following:
  • $A+B+C$ equals $9$ or $6$.
  • $(A^2+B^2)$%$C$ equals $9$ or $6$. If $C$ is $0$, then this condition is considered not satisfied.

Input Format

One line with two numbers $N$, $M$.

Output Format

One number, representing the count of such numbers.

3 1

16

Hint

For $10\%$ of the testdata, $N \le 6$.

For $40\%$ of the testdata, $N \le 18$.

For $100\%$ of the testdata, $N \le 50$, $0 \le M \le N$.

Translated by ChatGPT 5