Pasha and Phone

题意翻译

## 题目描述 让你构造长度为 n 的电话号码，满足将其均分成 k 段后，第 i 段能被 $a_i$ 整除且开头不为 $b_i$ 的个数总和，答案对 $10^9+7$取模。 ## 输入格式 第一行两个整数$n,k( 1<=n<=100000, 1<=k<=min(n,9))$。 第二行$n/k$个数，表示$a_i$。 第三行$n/k$个数，表示$b_i$。 ## 输出格式 一个整数，电话号码情况总数。

题目描述

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<=100000 $ , $ 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}&lt;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 $ .

输入输出样例

输入样例 #1

6 2
38 56 49
7 3 4

输出样例 #1

8

输入样例 #2

8 2
1 22 3 44
5 4 3 2

输出样例 #2

32400

说明

In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.