CF595B Pasha and Phone

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

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.