# -*- coding: utf-8 -*-

class Solution:
    """
    @param key: A String you should hash
    @param HASH_SIZE: An integer
    @return an integer
    """
    def hashCode(self, key, HASH_SIZE):
        # write your code here
        x = 0
        for i in xrange(len(key)):
            x += ord(key[i]) * self.fastPower(33, HASH_SIZE, len(key) - 1 - i)
        return x % HASH_SIZE
        
    def fastPower(self, a, b, n): # 参考fast_power.py实现快速取模
        # write your code here
        if n == 0:
            return 1 % b
        if 1 == n:
            return a % b
        x = self.fastPower(a, b, n / 2)
        if n % 2 == 1:
            return (((x * x) % b) * a) % b
        else:
            return (x * x) % b