Triângulo Trinomial, a Vingança

O triângulo trinomial é um triângulo numérico de coeficientes trinomiais. Ele pode ser obtido com uma linha contendo um único "1", a próxima linha contendo três 1 e cada elemento das linhas seguintes sendo calculado como a soma do elemento acima à esquerda, imediatamente acima e acima à direita:

A primeira linha do triângulo trinomial é numerada com zero, a segunda linha é a de número 1 e assim sucessivamente.

Sua tarefa é, dado um número de linha R, escrever um programa que exiba a soma de seus elementos. Por exemplo, a soma dos elementos da linha 2 é 9 = 1 + 2 + 3 + 2 + 1.

Mas desta vez o número de linha R pode ser muito maior! Sendo assim, a soma dos elementos da linha R deve ser mostrada módulo (2³¹ - 1). Por exemplo, a soma dos elementos da linha 20 é 3486784401 mas a resposta a ser dada é 1339300754, que é congruente a 3486784401 módulo (2³¹ - 1).