407233: GYM102700 C Cipher count

The Vigenère cipher is a very famous method for encrypting messages using polyalphabetic substitution, this method is a generalization of Cesar's cipher or ROT cipher, which do shifts of the letter over an alphabet. Formally, Vigenère works as follows:

Let $$$\Sigma$$$ be the alphabet of size $$$a$$$, which can be mapped to numbers $$$0,1,...,a-1$$$. let $$$m = m_1m_2...m_n$$$ be a message of size $$$n$$$, using the letters from $$$\Sigma$$$, and $$$k = k_1k_2...k_t$$$ the key of size $$$t$$$, using also letters from $$$\Sigma$$$. To encrypt, we concatenate $$$k$$$ to itself multiple times until it has size $$$n$$$, then we shift each letter in $$$m$$$ some positions to the right in the alphabet according to the letter of the repeated key, i.e. for each letter $$$m_i$$$ we take the letter in the alphabet that is $$$k_i$$$ positions to the right cyclically. To decrypt, we do the same procedure but shifting the letters to the left instead.

For example, take the 26 letters of the English alphabet from A to Z, where A is mapped to 0, B is mapped to 1, and so on, Z is mapped to 25. We want to encrypt the message $$$m=$$$ MESSAGE of size 7 using the key $$$k=$$$ KEY of size 3, first we concatenate $$$k$$$ multiple times until its size is 7, obtaining KEYKEYK. Then we shift each letter in $$$m$$$ in the alphabet according to the repeated key. For instance, the first M in the message is shifted K positions (10 positions) in the alphabet mapping it to the letter W. Note that the shifting is cyclic, therefore after letter Z goes letter A. The whole encryption process look like this:

Note that Vigenère cipher, as most symmetric ciphers, depends only on the key. Thus, if an attacker is able to get the correct key, the attacker could read every encrypted juicy message.

Now, an attacker knows the size of the alphabet $$$a$$$ and the maximum size of the key. What is the minimum number of keys the attacker has to try, to be sure to get a key which can decrypt any message sent by the sender?

The input consists of 2 numbers $$$a$$$ ($$$1 \leq a \leq 10^3$$$) and $$$k$$$ ($$$1 \leq k \leq 5*10^6$$$) — The size of the alphabet and the maximum size of the key, respectively.

Print one single number, the number of keys the attacker should try to be sure he (or she) can decrypt correctly any message.

As this number can be very large print it modulo $$$10^9 + 7$$$.

26 1

26

2 2

4

1 3

1

For the first sample, consider the English alphabet of size a = 26 and a maximum key size k = 1. The attacker has to try 26 possible keys: a, b, c,..., z.

For the second sample, consider the binary alphabet {0, 1} of size a = 2 and a maximum key size k = 2. The attacker can decrypt any message after trying only 4 keys: 0, 1, 01 and 10. Note that it is not necessary to try key 00, as any message encrypted with key 00 can be decrypted with key 0, it is not necessary to try key 11 neither.