Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly n digits. 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. 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 . 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 10 9 + 7 . 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 . 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 ). 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 ). Print a single integer — the number of good phone numbers of length n modulo 10 9 + 7 . In the first test sample good phone numbers are: 000000 , 000098 , 005600 , 005698 , 380000 , 380098 , 385600 , 385698 .