595B.md (2353B)
1 Source: https://codeforces.com/problemset/problem/595/B 2 3 B. Pasha and Phone 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly *n* digits. 22 23 Also Pasha has a number *k* and two sequences of length *n* / *k* (*n* is divisible by *k*) *a*1, *a*2, ..., *a**n* / *k* and *b*1, *b*2, ..., *b**n* / *k*. Let's split the phone number into blocks of length *k*. The first block will be formed by digits from the phone number that are on positions 1, 2,..., *k*, the second block will be formed by digits from the phone number that are on positions *k* + 1, *k* + 2, ..., 2·*k* and so on. Pasha considers a phone number good, if the *i*-th block doesn't start from the digit *b**i* and is divisible by *a**i* if represented as an integer. 24 25 To represent the block of length *k* as an integer, let's write it out as a sequence *c*1, *c*2,...,*c**k*. Then the integer is calculated as the result of the expression *c*1·10*k* - 1 + *c*2·10*k* - 2 + ... + *c**k*. 26 27 Pasha asks you to calculate the number of good phone numbers of length *n*, for the given *k*, *a**i* and *b**i*. As this number can be too big, print it modulo 109 + 7. 28 29 Input 30 31 The first line of the input contains two integers *n* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ *min*(*n*, 9)) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that *n* is divisible by *k*. 32 33 The second line of the input contains *n* / *k* space-separated positive integers — sequence *a*1, *a*2, ..., *a**n* / *k* (1 ≤ *a**i* < 10*k*). 34 35 The third line of the input contains *n* / *k* space-separated positive integers — sequence *b*1, *b*2, ..., *b**n* / *k* (0 ≤ *b**i* ≤ 9). 36 37 Output 38 39 Print a single integer — the number of good phone numbers of length *n* modulo 109 + 7. 40 41 Examples 42 43 Input 44 45 ``` 46 6 2 47 38 56 49 48 7 3 4 49 ``` 50 51 Output 52 53 ``` 54 8 55 ``` 56 57 Input 58 59 ``` 60 8 2 61 1 22 3 44 62 5 4 3 2 63 ``` 64 65 Output 66 67 ``` 68 32400 69 ``` 70 71 Note 72 73 In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.