{"problem":{"name":"C. Cipher count","description":{"content":"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 ov","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10270C"},"statements":[{"statement_type":"Markdown","content":"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:\n\nLet $Sigma$ be the alphabet of size $a$, which can be mapped to numbers $0, 1,..., a -1$. let $m = m_1 m_2... m_n$ be a message of size $n$, using the letters from $Sigma$, and $k = k_1 k_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.\n\nFor 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:\n\nNote 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.\n\nNow, 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?\n\nThe input consists of 2 numbers $a$ ($1 <= a <= 10^3$) and $k$ ($1 <= k <= 5 * 10^6$) — The size of the alphabet and the maximum size of the key, respectively.\n\nPrint one single number, the number of keys the attacker should try to be sure he (or she) can decrypt correctly any message.\n\nAs this number can be very large print it modulo $10^9 + 7$.\n\nFor 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.\n\nFor 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.\n\n## Input\n\nThe input consists of 2 numbers $a$ ($1 <= a <= 10^3$) and $k$ ($1 <= k <= 5 * 10^6$) — The size of the alphabet and the maximum size of the key, respectively.\n\n## Output\n\nPrint 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$.\n\n[samples]\n\n## Note\n\nFor 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P \\in \\mathbb{Z}^+ $ be the number of positive words.  \nLet $ \\mathcal{P} = \\{p_1, p_2, \\dots, p_P\\} $ be the set of positive words.  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of negative words.  \nLet $ \\mathcal{N} = \\{n_1, n_2, \\dots, n_N\\} $ be the set of negative words.  \nLet $ W \\in \\mathbb{Z}^+ $ be the number of words in the feedback.  \nLet $ F = (f_1, f_2, \\dots, f_W) $ be the sequence of words in the feedback.\n\n**Constraints**  \n1. $ 1 \\leq P \\leq 100 $  \n2. $ 1 \\leq N \\leq 100 $  \n3. $ 1 \\leq W \\leq 1000 $  \n4. $ \\mathcal{P} \\cap \\mathcal{N} = \\emptyset $\n\n**Objective**  \nLet $ c_P = \\left| \\{ f_i \\mid f_i \\in \\mathcal{P} \\} \\right| $ be the count of positive words in $ F $.  \nLet $ c_N = \\left| \\{ f_i \\mid f_i \\in \\mathcal{N} \\} \\right| $ be the count of negative words in $ F $.  \n\nOutput:  \n- $ \\text{Positive} $ if $ c_P > c_N $,  \n- $ \\text{Negative} $ if $ c_P < c_N $,  \n- $ \\text{Neutral} $ if $ c_P = c_N $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10270C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}