АПО. База: Пробный муниципальный этап. Старшая группа.

В фантастическом романе, который пишет Петя Торопыжкин, инопланетные существа используют алфавит, состоящий из двух символов и Которые в рабочем варианте текста Петя представляет заглавными буквами F и G (для простоты). Петя даже составил словарь языка этих существ. Для быстроты поиска по словарю он выбрал целое число \(p\) и сопоставил каждому слову \(w=\alpha_0\alpha_1\ldots\alpha_k\) целое число \(h(w) = \sum_{i=0}^k a_i \cdot p^i\), где коэффициент \(a_i\) равен \(0\), если \(\alpha_i = F\), и \(1\), если \(\alpha_i = G\). Однако такое число может быть большим, поэтому Петя запоминает остаток от деления \(h(w)\) на число \(D = 10^9 + 7\).

Такое число называется хешем слова \(w\), а правило вычисления хеша — хеш-функ-ци-ей . Вычислив один раз хеши слов из словаря, дальше очень просто проверять их на несовпадение: если хеши двух слов различаются, то и сами слова совпадать не могут. А вот если хеши двух слов совпадают (такую ситуацию называют коллизией ), тогда для точной проверки эти слова надо сравнивать посимвольно.

Для работы со словарём нужна программа, по заданному слову находящую его хеш.