{"raw_statement":[{"iden":"problem statement","content":"In this problem, hexadecimal notations use `0`, ..., `9`, `A`, ..., `F`, representing the values zero through fifteen, respectively.  \nUnless otherwise specified, all notations of numbers are decimal notations.\nHow many integers between $1$ and $N$ (inclusive) have exactly $K$ distinct digits in the hexadecimal notation without leading zeros?  \nPrint this count modulo $(10^9 + 7)$."},{"iden":"constraints","content":"*   $1 \\le N \\lt {16}^{2 \\times 10^5}$\n*   $N$ is given in hexadecimal notation without leading `0`s.\n*   $1 \\le K \\le 16$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n\nHere, $N$ is in hexadecimal notation."},{"iden":"sample input 1","content":"10 1"},{"iden":"sample output 1","content":"15\n\nThe hexadecimal number $N$ is $16$ in decimal.  \nIn hexadecimal, the integers between $1$ and $16$ are written as follows:\n\n*   $1$ through $15$: are $1$\\-digit numbers in hexadecimal, containing one distinct digit.\n*   $16$: is $10$ in hexadecimal, containing two distinct digits.\n\nThus, there are $15$ numbers that contain one distinct digit in hexadecimal."},{"iden":"sample input 2","content":"FF 2"},{"iden":"sample output 2","content":"225\n\nAll of the $255$ numbers except the following $30$ numbers contain two distinct digits in hexadecimal: $1, 2, 3, \\dots, \\mathrm{E}, \\mathrm{F}, 11, 22, 33, \\dots, \\mathrm{EE}, \\mathrm{FF}$ in hexadecimal."},{"iden":"sample input 3","content":"100 2"},{"iden":"sample output 3","content":"226"},{"iden":"sample input 4","content":"1A8FD02 4"},{"iden":"sample output 4","content":"3784674"},{"iden":"sample input 5","content":"DEADBEEFDEADBEEEEEEEEF 16"},{"iden":"sample output 5","content":"153954073\n\nPrint the count modulo $(10^9 + 7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}