{"problem":{"name":"J. Math Homework","description":{"content":"Yes, your teacher gave you another hard math homework, and you have to finish it before its deadline. This homework is about the division operation, and it's a practice for the division by small numb","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10015J"},"statements":[{"statement_type":"Markdown","content":"Yes, your teacher gave you another hard math homework, and you have to finish it before its deadline.\n\nThis homework is about the division operation, and it's a practice for the division by small numbers. You are asked to count the non-negative numbers which consist of exactly *N* digits (leading zeros are allowed), and they satisfy some division requirements, for example let's say you want to count the numbers which consist of 2 digits and they are divisible by 6 and not divisible by 5, these are the numbers which satisfy these requirements: 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 and 96.\n\nNote that zero is divisible by any positive number (check the third sample test case). \n\nSo, you decided to write a program to solve this homework for you, because *N* can be really large.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  10). Followed by *T* lines, each line represents one test case, and consists of an integer *N* (1  ≤  *N*  ≤  1018) which is the length of the numbers you are asked to count (again, leading zeros are allowed) followed by a space then a string of 6 digits (each digit is '0', '1' or '2'), the *ith* digit (the left most digit is the digit number 1) is '0' if the numbers shouldn't be divisible by *i*, and it's '1' if the numbers should be divisible by *i*, and it's '2' if the numbers can be divisible or not divisible by *i*.\n\nFor each test case, print on a single line one integer, the count of the numbers you are asked to count as described above, since the result may be very large, print it modulo 1,000,000,007 (109 + 7).\n\n## Input\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  10). Followed by *T* lines, each line represents one test case, and consists of an integer *N* (1  ≤  *N*  ≤  1018) which is the length of the numbers you are asked to count (again, leading zeros are allowed) followed by a space then a string of 6 digits (each digit is '0', '1' or '2'), the *ith* digit (the left most digit is the digit number 1) is '0' if the numbers shouldn't be divisible by *i*, and it's '1' if the numbers should be divisible by *i*, and it's '2' if the numbers can be divisible or not divisible by *i*.\n\n## Output\n\nFor each test case, print on a single line one integer, the count of the numbers you are asked to count as described above, since the result may be very large, print it modulo 1,000,000,007 (109 + 7).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ with $ 1 \\le N_k \\le 10^{18} $ be the number of digits.  \n- Let $ D_k = d_{k,1}d_{k,2}d_{k,3}d_{k,4}d_{k,5}d_{k,6} \\in \\{0,1,2\\}^6 $ be a constraint string, where:  \n  - $ d_{k,i} = 0 $: numbers must **not** be divisible by $ i $,  \n  - $ d_{k,i} = 1 $: numbers must be **divisible** by $ i $,  \n  - $ d_{k,i} = 2 $: no constraint on divisibility by $ i $.  \n\nLet $ \\mathcal{S}_k $ be the set of all $ N_k $-digit numbers (with leading zeros allowed) over $ \\{0,1,\\dots,9\\}^{N_k} $, interpreted as integers in $ [0, 10^{N_k} - 1] $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $  \n2. $ 1 \\le N_k \\le 10^{18} $ for all $ k $  \n3. $ d_{k,i} \\in \\{0,1,2\\} $ for all $ i \\in \\{1,2,3,4,5,6\\} $\n\n**Objective**  \nFor each test case $ k $, compute:  \n$$\n\\left| \\left\\{ x \\in [0, 10^{N_k} - 1] \\,\\middle|\\, \\forall i \\in \\{1,2,3,4,5,6\\},\\ \n\\begin{cases}\ni \\nmid x & \\text{if } d_{k,i} = 0 \\\\\ni \\mid x & \\text{if } d_{k,i} = 1 \\\\\n\\text{no constraint} & \\text{if } d_{k,i} = 2\n\\end{cases}\n\\right\\} \\right| \\mod 1000000007\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10015J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}