。。。。。。。。。。。谁能看懂我的抓狂！（点击标题查看更多。。）

 

PS：

A题是算几个10^6以内的组合数的和，复杂度是两千万，Python果断超时，换了C++，同样的代码156ms瞬间搞定。。

遂持C++进入B题（C题是两行代码，还是Python快些），是分解质因数然后挨家寻访，复杂度七百万，我自豪地看着C++，但是出乎意料地还是超了。。（有趣的是C++17挣扎着又迈了两步，有PyPy“熊风”）我很奇怪，因为我这儿的编译器明明很快，故疯狂测试、不得其解。快结束的时候想起一位同学提起过C的任性，遂又转成了C（没用C写过东西，竟然没有bool。。当然，Google一下我就知道），居然秒过了。。。我现在觉得是C++里那个cin和cout根本处理不了10^6个输入数据，输入即超时。。

这一场下来，我被迫从Python转到C++，又被迫从C++转到C！这是一场劝退课……经此役后，Python与C++士气大减。但C++可以五十步笑百步：Python比我，就如同我比C——那可是：繁星比皓月！

 

PS^2：附ABC三题。。不知多年以后的计算机能否迅速算出这些…（那时可能就是mod 10^7567588+7了）

 

A. Vitaly is a very weird man. He’s got two favorite digits a and b. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits a and b. Vitaly calls a good number excellent, if the sum of its digits is a good number.

For example, let’s say that Vitaly’s favourite digits are 1 and 3, then number 12 isn’t good and numbers 13 or 311 are. Also, number 111 is excellent and number 11 isn’t.

Now Vitaly is wondering, how many excellent numbers of length exactly n are there. As this number can be rather large, he asks you to count the remainder after dividing it by 1000000007 (10^9 + 7).

A number’s length is the number of digits in its decimal representation without leading zeroes.

Input
The first line contains three integers: a, b, n (1 ≤ a < b ≤ 9, 1 ≤ n ≤ 10^6).

Output
Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7).

Examples
input
1 3 3
output
1
input
2 3 10
output
165

 

B. Today Pari and Arya are playing a game called Remainders.

Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value . There are n ancient numbers c1, c2, …, cn and Pari has to tell Arya if Arya wants. Given k and the ancient values, tell us if Arya has a winning strategy independent of value of x or not. Formally, is it true that Arya can understand the value for any positive integer x?

Note, that means the remainder of x after dividing it by y.

Input
The first line of the input contains two integers n and k (1 ≤ n,  k ≤ 1 000 000) — the number of ancient integers and value k that is chosen by Pari.

The second line contains n integers c1, c2, …, cn (1 ≤ ci ≤ 1 000 000).

Output
Print “Yes” (without quotes) if Arya has a winning strategy independent of value of x, or “No” (without quotes) otherwise.

Examples
input
4 5
2 3 5 12
output
Yes
input
2 7
2 3
output
No

 

C. Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let’s number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place have ai coins. If there is an integer i (0 ≤ i < n) such that ai + a(i+n) + a(i+2n) ≠ 6, then Tanya is satisfied.

Count the number of ways to choose ai so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 10^9 + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3n), such that ai ≠ bi (that is, some gnome got different number of coins in these two ways).

Input
A single line contains number n (1 ≤ n ≤ 10^5) — the number of the gnomes divided by three.

Output
Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 10^9 + 7.

Examples
input
1
output
20
input
2
output
680