It looks like `d` is defined modulo `q`, yet the definition (a few lines above) doesn't reduce it.

Might be worth changing the line to 

```python
d = -121665 * inv(121666) % q
```

Which should give you a speedup.